Difficulty: Hard
Language: Java
Topics: Arrays, Two Pointers, Binary Search
Optimal Time Complexity: O(log(min(m, n)))
Optimal Space Complexity: O(1)
Introduction
Median of Two Sorted Arrays is LeetCode Problem #4 and is one of the most popular binary-search problems asked in coding interviews.
At first, the problem looks simple. We have two sorted arrays, so we might think:
“Why don’t we just combine them and find the middle?”
That approach works, but it does not satisfy the optimal time-complexity requirement.
The real challenge is to solve the problem without actually merging the arrays.
In this article, we’ll understand the problem step by step and move from:
Brute Force → Better Approach → Optimal Binary Search
Problem Statement
Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays.
The overall runtime complexity should be:
O(log(m + n))
where m and n are the lengths of the two arrays.
Example 1
nums1 = [1, 3]
nums2 = [2]
If we combine the arrays:
[1, 2, 3]
There are 3 elements.
The middle element is:
2
Therefore:
Answer = 2
Example 2
nums1 = [1, 3]
nums2 = [2, 4]
Combined:
[1, 2, 3, 4]
There are 4 elements, so there are two middle elements:
2 and 3
Therefore:
Median = (2 + 3) / 2
= 2.5
Answer = 2.5
First Understand What a Median Is
Before solving the problem, let’s understand the median.
Case 1: Odd Number of Elements
Consider:
[1, 2, 3, 4, 5]
There are 5 elements.
The middle element is:
3
Therefore:
Median = 3
Case 2: Even Number of Elements
Consider:
[1, 2, 3, 4]
There are 4 elements.
The two middle elements are:
2 and 3
Therefore:
Median = (2 + 3) / 2
= 2.5
Simple Rule
For an odd number of elements:
Median = Middle element
For an even number of elements:
Median = Average of the two middle elements
Approach 1 — Brute Force
The easiest solution is to actually combine both arrays.
For example:
nums1 = [1, 3]
nums2 = [2, 4]
We create:
merged = [1, 2, 3, 4]
Then we find the median.
Because both arrays are already sorted, we can merge them using the same technique used in the Merge Sort algorithm.
Brute Force Java Solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] merged = new int[m + n];
int i = 0;
int j = 0;
int k = 0;
// Merge both sorted arrays
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
merged[k] = nums1[i];
i++;
} else {
merged[k] = nums2[j];
j++;
}
k++;
}
// Remaining elements of nums1
while (i < m) {
merged[k] = nums1[i];
i++;
k++;
}
// Remaining elements of nums2
while (j < n) {
merged[k] = nums2[j];
j++;
k++;
}
// Find median
int total = m + n;
if (total % 2 == 1) {
return merged[total / 2];
}
return (merged[total / 2 - 1]
+ merged[total / 2]) / 2.0;
}
}
Brute Force Dry Run
Let’s take:
nums1 = [1, 3]
nums2 = [2, 4]
Initially:
i = 0
j = 0
k = 0
We compare:
nums1[i] = 1
nums2[j] = 2
Since:
1 < 2
we put 1 into the merged array.
merged = [1]
Move i:
i = 1
Next:
nums1[i] = 3
nums2[j] = 2
Since 2 is smaller:
merged = [1, 2]
Move j:
j = 1
Next:
nums1[i] = 3
nums2[j] = 4
So we take 3:
merged = [1, 2, 3]
Finally, 4 is remaining:
merged = [1, 2, 3, 4]
Now:
total = 4
Since 4 is even, we take:
merged[1] = 2
merged[2] = 3
Therefore:
Median = (2 + 3) / 2.0
= 2.5
Complexity of Brute Force
We visit all the elements while merging.Time Complexity
O(m + n)
Space Complexity
We create a new array containing all elements.
O(m + n)
This solution is easy to understand, but it is not optimal.
The problem asks for a logarithmic solution.
Approach 2 — Two Pointers Without Creating a New Array
Can we improve the brute-force solution?
Yes.
We don’t actually need to store the complete merged array.
We only need to reach the middle element or the two middle elements.
So we can use two pointers:
i → nums1
j → nums2
At every step, we take the smaller element.
We continue only until we reach the middle.
This removes the extra array.
Two-Pointer Java Solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int total = m + n;
int i = 0;
int j = 0;
int previous = 0;
int current = 0;
// Move only until the middle
for (int count = 0; count <= total / 2; count++) {
previous = current;
if (i < m && (j >= n || nums1[i] <= nums2[j])) {
current = nums1[i];
i++;
} else {
current = nums2[j];
j++;
}
}
// Odd number of elements
if (total % 2 == 1) {
return current;
}
// Even number of elements
return (previous + current) / 2.0;
}
}
Why Do We Need previous and current?
Consider:
[1, 2, 3, 4]
The middle elements are:
2 and 3
When our pointers move through the arrays:
1 → 2 → 3
When we reach 3:
previous = 2
current = 3
So for an even number of elements:
Median = (previous + current) / 2.0
For an odd number of elements, current itself is the median.
Complexity of the Two-Pointer Approach
We still move through the arrays until the middle.
Therefore:
Time Complexity
O(m + n)
Space Complexity
We only use a few variables.
O(1)
This is better than the brute-force solution because we have reduced the space from O(m + n) to O(1).
But the time complexity is still not logarithmic.
Now let’s move to the optimal solution.
Approach 3 — Optimal Binary Search
This is the most important approach.
The key idea is:
We don’t need to merge the arrays. We only need to find the correct partition.
Imagine dividing all the elements into two halves:
LEFT HALF | RIGHT HALF
For example:
[1, 2] | [3, 4]
The left half contains the smaller elements.
The right half contains the larger elements.
If we can find this partition directly, we can find the median without merging the arrays.
Partitioning the Two Arrays
Suppose:
nums1 = [1, 3]
nums2 = [2, 4]
We want to divide them like this:
nums1 = [1 | 3]
nums2 = [2 | 4]
Together:
LEFT = [1, 2]
RIGHT = [3, 4]
So the combined structure is:
[1, 2] | [3, 4]
This is the correct partition.
Understanding the Four Important Values
Let’s give names to the values around the partitions:
nums1 = [ Aleft | Aright ]
nums2 = [ Bleft | Bright ]
For:
nums1 = [1 | 3]
nums2 = [2 | 4]
we have:
Aleft = 1
Aright = 3
Bleft = 2
Bright = 4
These four values are the most important part of the optimal solution.
When Is the Partition Correct?
The partition is correct when:
Aleft <= Bright
AND:
Bleft <= Aright
For our example:
Aleft = 1
Bright = 4
1 <= 4 ✓
And:
Bleft = 2
Aright = 3
2 <= 3 ✓
Both conditions are true.
Therefore, the partition is correct.
Why Do We Only Check These Two Conditions?
Both arrays are already sorted.
Therefore, inside nums1:
Aleft <= Aright
is automatically true.
And inside nums2:
Bleft <= Bright
is automatically true.
The only possible problem is between the two arrays.
So we only need to check:
Aleft <= Bright
and:
Bleft <= Aright
If both are true, we have successfully divided the combined array into two sorted halves.
How Many Elements Should Be on the Left?
Suppose:
m = nums1.length
n = nums2.length
The total number of elements is:
m + n
We calculate:
int half = (m + n + 1) / 2;
For example:
m = 2
n = 2
Then:
half = (2 + 2 + 1) / 2
= 5 / 2
= 2
Therefore, we need 2 elements on the left.
Why Do We Add +1?
The +1 helps us handle odd-length arrays.
Consider:
nums1 = [1, 3]
nums2 = [2]
Combined:
[1, 2, 3]
There are 3 elements.
We want:
[1, 2] | [3]
The left side has 2 elements.
Our formula gives:
half = (3 + 1) / 2
= 2
Therefore, the extra element goes to the left side.
This makes the odd and even cases easier to handle.
Why Do We Binary Search Only One Array?
Suppose we choose a partition in nums1.
Let:
i = number of elements taken from nums1
If we know the total number of elements required on the left, then the partition in nums2 is automatically determined.
If:
i + j = half
then:
j = half - i
Therefore:
int j = half - i;
This is one of the most important lines in the solution.
Once we choose i, we automatically know j.
That’s why we only need to binary search one array.
Why Binary Search the Smaller Array?
Before starting binary search, we make sure that nums1 is the smaller array.
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
After this:
nums1.length <= nums2.length
Now the binary search operates on the smaller array.
This gives us:
O(log(min(m, n)))
time complexity.
Binary Search Range
We use:
int left = 0;
int right = m;
Why?
Suppose:
nums1 = [1, 3]
Possible partitions are:
| 1 3
1 | 3
1 3 |
Their partition positions are:
0
1
2
Since:
m = 2
our search range is:
0 to 2
Therefore:
left = 0;
right = m;
Finding the Partition
Inside the binary search:
int i = (left + right) / 2;
Suppose:
left = 0
right = 2
Then:
i = (0 + 2) / 2
= 1
So:
nums1 = [1 | 3]
Now calculate the partition in nums2:
int j = half - i;
If:
half = 2
i = 1
then:
j = 2 - 1
= 1
Therefore:
nums1 = [1 | 3]
nums2 = [2 | 4]
Finding Aleft and Aright
We need:
Aleft
Aright
The code is:
int Aleft = (i == 0)
? Integer.MIN_VALUE
: nums1[i - 1];
int Aright = (i == m)
? Integer.MAX_VALUE
: nums1[i];
Normally:
Aleft = nums1[i - 1]
Aright = nums1[i]
For:
nums1 = [1 | 3]
we get:
Aleft = 1
Aright = 3
Why Integer.MIN_VALUE?
Consider this partition:
| 1 3
There is no element on the left.
Therefore, Aleft doesn’t exist.
Instead of writing complicated special cases, we use:
Integer.MIN_VALUE
This behaves like negative infinity for our comparison.
So:
Aleft = -∞
Why Integer.MAX_VALUE?
Now consider:
1 3 |
There is no element on the right.
So we use:
Integer.MAX_VALUE
This behaves like positive infinity.
Therefore:
Aright = +∞
This allows the same logic to work even when the partition is at the beginning or end of an array.
Finding Bleft and Bright
We do the same thing for nums2:
int Bleft = (j == 0)
? Integer.MIN_VALUE
: nums2[j - 1];
int Bright = (j == n)
? Integer.MAX_VALUE
: nums2[j];
For:
nums2 = [2 | 4]
we get:
Bleft = 2
Bright = 4
Now we have:
Aleft = 1
Aright = 3
Bleft = 2
Bright = 4
The Complete Optimal Java Solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Always binary search on the smaller array
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
// Binary search range
int left = 0;
int right = m;
// Number of elements needed on the left
int half = (m + n + 1) / 2;
while (left <= right) {
// Partition nums1
int i = (left + right) / 2;
// Partition nums2
int j = half - i;
// Boundary values of nums1
int Aleft = (i == 0)
? Integer.MIN_VALUE
: nums1[i - 1];
int Aright = (i == m)
? Integer.MAX_VALUE
: nums1[i];
// Boundary values of nums2
int Bleft = (j == 0)
? Integer.MIN_VALUE
: nums2[j - 1];
int Bright = (j == n)
? Integer.MAX_VALUE
: nums2[j];
// Correct partition
if (Aleft <= Bright && Bleft <= Aright) {
// Odd number of elements
if ((m + n) % 2 == 1) {
return Math.max(Aleft, Bleft);
}
// Even number of elements
return (Math.max(Aleft, Bleft)
+ Math.min(Aright, Bright)) / 2.0;
}
// Partition in nums1 is too far right
else if (Aleft > Bright) {
right = i - 1;
}
// Partition in nums1 is too far left
else {
left = i + 1;
}
}
return 0.0;
}
}
Complete Dry Run of the Optimal Solution
Let’s use:
nums1 = [1, 3]
nums2 = [2, 4]
Step 1 — Lengths
m = 2
n = 2
Both arrays have the same size, so no swapping is needed.
Step 2 — Initialize Binary Search
left = 0
right = 2
Calculate:
half = (2 + 2 + 1) / 2
= 2
So we need 2 elements on the left.
Step 3 — Find i
i = (left + right) / 2
i = (0 + 2) / 2
i = 1
Therefore:
nums1 = [1 | 3]
Step 4 — Find j
j = half - i
j = 2 - 1
j = 1
Therefore:
nums2 = [2 | 4]
Step 5 — Boundary Values
Aleft = 1
Aright = 3
Bleft = 2
Bright = 4
Step 6 — Check the Partition
First condition:
Aleft <= Bright
1 <= 4 ✓
Second condition:
Bleft <= Aright
2 <= 3 ✓
Both conditions are true.
Therefore:
We found the correct partition.
The combined array can be thought of as:
[1, 2] | [3, 4]
Step 7 — Calculate the Median
Total number of elements:
m + n = 4
4 is even.
The largest element on the left is:
max(Aleft, Bleft)
max(1, 2)
= 2
The smallest element on the right is:
min(Aright, Bright)
min(3, 4)
= 3
Therefore:
Median = (2 + 3) / 2.0
= 2.5
Final Answer = 2.5
What Happens If the Partition Is Wrong?
There are two possibilities.
Case 1 — Partition Is Too Far Right
Suppose:
Aleft > Bright
For example:
Aleft = 8
Bright = 5
That means we have taken too many elements from nums1.
The partition in nums1 needs to move left.
Therefore:
right = i - 1;
Case 2 — Partition Is Too Far Left
Suppose:
Bleft > Aright
For example:
Bleft = 10
Aright = 4
That means we have taken too few elements from nums1.
We need to move the partition in nums1 to the right.
Therefore:
left = i + 1;
This is the binary-search part of the algorithm.
Odd Number of Elements
Consider:
nums1 = [1, 3]
nums2 = [2]
Combined:
[1, 2, 3]
Correct partition:
[1, 2] | [3]
The left side contains the extra element.
Therefore, the median is the largest element on the left:
max(Aleft, Bleft)
In this case:
max(1, 2) = 2
So:
Median = 2
Even Number of Elements
Consider:
nums1 = [1, 3]
nums2 = [2, 4]
Correct partition:
[1, 2] | [3, 4]
The two middle elements are:
2 and 3
The largest element on the left:
max(Aleft, Bleft)
The smallest element on the right:
min(Aright, Bright)
Therefore:
Median =
(max(Aleft, Bleft) + min(Aright, Bright)) / 2.0
Why Do We Use 2.0 Instead of 2?
This is an important Java detail.
If we write:
5 / 2
Java performs integer division:
2
But we need:
2.5
Therefore, we use:
5 / 2.0
Now Java performs floating-point division:
2.5
That’s why our solution uses:
/ 2.0
instead of:
/ 2
Comparing All Three Approaches
| Approach | Technique | Time Complexity | Space Complexity |
|---|---|---|---|
| Brute Force | Merge arrays | O(m + n) | O(m + n) |
| Better | Two pointers | O(m + n) | O(1) |
| Optimal | Binary Search | O(log(min(m, n))) | O(1) |
Progression
Brute Force
↓
Merge both arrays
↓
O(m+n) time
O(m+n) space
↓
Better
↓
Two pointers
↓
O(m+n) time
O(1) space
↓
Optimal
↓
Binary Search
↓
O(log(min(m,n))) time
O(1) space
The Most Important Part to Remember
You do not need to memorize the entire optimal code.
Remember this diagram:
nums1 = [ Aleft | Aright ]
nums2 = [ Bleft | Bright ]
Then remember the correct-partition conditions:
Aleft <= Bright
Bleft <= Aright
And remember:
i + j = half
Therefore:
j = half - i
Once the partition is correct:
Odd
median = max(Aleft, Bleft)
Even
median =
(max(Aleft, Bleft)
+ min(Aright, Bright)) / 2.0
Interview-Friendly Explanation
If an interviewer asks you to explain your solution, you can say:
“Since both arrays are sorted, I don’t need to merge them. I binary-search the smaller array to find a partition such that the combined left half contains half of the elements. If
ielements are taken from the first array, thenj = half - ielements must be taken from the second array. The partition is valid whenAleft <= BrightandBleft <= Aright. Once the partition is valid, for an odd total length the median is the maximum element on the left, and for an even total length it is the average of the maximum element on the left and the minimum element on the right.”
This is a very good explanation to use in an interview.
Final Mental Model
Think of the problem as finding this dividing line:
LEFT RIGHT
nums1 [---------- | ----------------]
↑
i
nums2 [---------- | ----------------]
↑
j
We need exactly half of the elements on the left:
i + j = half
Therefore:
j = half - i
Then check:
Aleft <= Bright
Bleft <= Aright
If the partition is correct, calculate the median.
If the partition is wrong:
Aleft > Bright
↓
Move partition LEFT
right = i - 1
or:
Bleft > Aright
↓
Move partition RIGHT
left = i + 1
Final Takeaway
The most important lesson from LeetCode #4 is:
Don’t merge the arrays. Find the correct partition.
The progression is:
Brute Force
Merge the arrays:
O(m+n) time
O(m+n) space
Better
Use two pointers:
O(m+n) time
O(1) space
Optimal
Binary search the partition:
O(log(min(m,n))) time
O(1) space
The three formulas worth remembering are:
j = half - i
Aleft <= Bright
Bleft <= Aright
and:
Odd:
max(Aleft, Bleft)
Even:
(max(Aleft, Bleft) + min(Aright, Bright)) / 2.0
Once these three ideas are clear, the entire LeetCode #4 solution becomes much easier to understand and implement.