LeetCode 4, Median of Two Sorted Arrays, asks us to find the median of two already sorted arrays without actually merging them. The key idea is to use binary search on a partition so that the combined left and right halves contain the correct elements.
Instead of building a merged array in O(m + n), we can find the correct partition in O(log min(m,n)) time and O(1) extra space.
Problem Statement
You are given two arrays, nums1 and nums2, both sorted in ascending order. The arrays can have different sizes, and one of them can even be empty.
Your task is to return the median of all elements as if the two arrays were combined into one sorted array. The required runtime is logarithmic rather than linear.
Problem: LeetCode 4 — Median of Two Sorted Arrays
Difficulty: Hard
Topics: Array, Binary Search, Divide and Conquer
View the original problem on LeetCode
Examples
Example 1
Input:
nums1 = [1, 3]
nums2 = [2]
Output:
2.0
The sorted combination would be [1, 2, 3], so the middle value is 2.
Example 2
Input:
nums1 = [1, 2]
nums2 = [3, 4]
Output:
2.5
The combined sorted array is [1, 2, 3, 4]. Since there are four elements, the median is the average of the two middle values:
(2 + 3) / 2 = 2.5.
Constraints
- Both input arrays are sorted in ascending order.
- Either array can contain between 0 and 1000 elements.
- The two arrays together contain at least one element.
- Values can range from
-106to106. - The required runtime is logarithmic.
The important constraint is the logarithmic runtime. A normal merge would take O(m + n), so we need to use the fact that both arrays are already sorted.
LeetCode 4 Median of Two Sorted Arrays — Intuition
The first instinct is usually to merge the two arrays:
nums1 = [1, 2]
nums2 = [3, 4]
Merged = [1, 2, 3, 4]But we do not actually need the complete merged array. We only need to know where the middle of that array would be.
So instead of asking:
"How do I merge these arrays?"
we ask:
"Where should I cut each array so that everything on the left belongs to the first half?"
The Partition Idea
Imagine placing a partition inside each array:
nums1: [ 1 2 | 3 4 ]
↑
partition
nums2: [ 5 6 | 7 8 ]
↑
partition
LEFT | RIGHTEverything before the partition belongs to the left half, while everything after it belongs to the right half.
For a correct partition, two things must be true:
- The left side must contain exactly half of the total elements.
- Every element on the left must be less than or equal to every element on the right.
We Only Need Four Boundary Values
Because each individual array is already sorted, we do not need to compare every element. We only need the values immediately next to the two partitions.
nums1: [ ... maxLeft1 | minRight1 ... ]
nums2: [ ... maxLeft2 | minRight2 ... ]
LEFT | RIGHTThe partition is correct when:
maxLeft1 <= minRight2
AND
maxLeft2 <= minRight1Why are these two comparisons enough? Because values within each array are already sorted. The only possible problem is that an element from the left side of one array might be larger than an element from the right side of the other array.
Why Binary Search?
We can choose the partition position in the smaller array and calculate the required partition in the larger array. That means there is only one partition position we need to search for.
If the partition in the first array is too far right, we move it left. If it is too far left, we move it right. This is exactly the behavior binary search is designed for.
Too far right
↓
[ 1 2 3 | 4 5 ]
← move left
Correct
[ 1 2 | 3 4 5 ]
Too far left
↓
[ 1 | 2 3 4 5 ]
→ move rightApproach
Brute Force Approach
The straightforward solution is to merge the two sorted arrays and then find the middle element or middle two elements.
[1, 3] + [2, 4]
↓
[1, 2, 3, 4]
↓
median = (2 + 3) / 2 = 2.5This takes O(m + n) time because we have to process the elements while merging. That does not satisfy the logarithmic requirement.
Optimal Binary Search Approach
- Always binary search the smaller array.
- Choose a partition in the smaller array.
- Calculate the corresponding partition in the larger array.
- Check whether the four boundary values form a valid partition.
- If the partition is too far right, move left.
- If the partition is too far left, move right.
- Once the partition is valid, calculate the median from the boundary values.
Calculating the Partitions
Suppose the two arrays have lengths m and n.
The total number of elements is:
total = m + nWe want approximately half of these elements on the left:
half = Math.floor((m + n + 1) / 2)
If the partition in nums1 contains partition1 elements, then the partition in nums2 must contain:
partition2 = half - partition1This guarantees that the left side always contains the required number of elements.
Handling Array Boundaries
A partition can occur before the first element or after the last element. For example:
| 1 2 3
4 5 |If there is no element on the left, we treat the left value as negative infinity. If there is no element on the right, we treat the right value as positive infinity.
No left element → -Infinity
No right element → InfinityThis lets the same comparison logic work even when one partition is at an array boundary.
Finding the Median
Once we find a valid partition, the median is directly available from the four boundary values.
For an odd number of total elements, the left side contains one extra element. Therefore:
median = max(maxLeft1, maxLeft2)For an even number of elements, the median is the average of the largest value on the left and the smallest value on the right:
median =
(max(maxLeft1, maxLeft2)
+ min(minRight1, minRight2)) / 2Dry Run
Consider:
nums1 = [1, 2]
nums2 = [3, 4]
The total number of elements is 4, so the left side needs 2 elements.
We binary search the smaller array, nums1.
| Step | partition1 | partition2 | Boundary Values | Result |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 2 and 3 | 4 | Valid partition |
The partition looks like this:
nums1: [ 1 | 2 ]
nums2: [ 3 | 4 ]
LEFT | RIGHT
Left side = [1, 3]
Right side = [2, 4]
The largest value on the left is 3, while the smallest value on the right is 2.
That tells us this particular partition is actually invalid because:
maxLeft2 = 3
minRight1 = 2
3 <= 2 → false
Therefore, the partition in nums1 is too far to the right and must move left.
The next partition is:
nums1: [ | 1 2 ]
nums2: [ 3 4 | ]
Left side = [3, 4]
Right side = [1, 2]For this particular setup, the search bounds continue adjusting until the valid partition is found. The correct final partition is:
nums1: [ 1 2 | ]
nums2: [ | 3 4 ]
Combined:
[ 1 2 | 3 4 ]Now:
maxLeft1 = 2
maxLeft2 = -Infinity
minRight1 = Infinity
minRight2 = 3
So the two middle values are 2 and 3:
median = (2 + 3) / 2
= 2.5The important part of the dry run is not the individual arithmetic. The key idea is that binary search keeps moving the partition until the left side and right side are correctly ordered.
Solution Code — JavaScript
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
const m = nums1.length;
const n = nums2.length;
const total = m + n;
const half = Math.floor((total + 1) / 2);
let left = 0;
let right = m;
while (left <= right) {
const partition1 = Math.floor((left + right) / 2);
const partition2 = half - partition1;
const maxLeft1 = partition1 === 0
? -Infinity
: nums1[partition1 - 1];
const minRight1 = partition1 === m
? Infinity
: nums1[partition1];
const maxLeft2 = partition2 === 0
? -Infinity
: nums2[partition2 - 1];
const minRight2 = partition2 === n
? Infinity
: nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if (total % 2 === 1) {
return Math.max(maxLeft1, maxLeft2);
}
return (
Math.max(maxLeft1, maxLeft2) +
Math.min(minRight1, minRight2)
) / 2;
}
if (maxLeft1 > minRight2) {
right = partition1 - 1;
} else {
left = partition1 + 1;
}
}
};Solution Code — C#
public class Solution
{
public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
if (nums1.Length > nums2.Length)
{
return FindMedianSortedArrays(nums2, nums1);
}
int m = nums1.Length;
int n = nums2.Length;
int total = m + n;
int half = (total + 1) / 2;
int left = 0;
int right = m;
while (left <= right)
{
int partition1 = (left + right) / 2;
int partition2 = half - partition1;
int maxLeft1 = partition1 == 0
? int.MinValue
: nums1[partition1 - 1];
int minRight1 = partition1 == m
? int.MaxValue
: nums1[partition1];
int maxLeft2 = partition2 == 0
? int.MinValue
: nums2[partition2 - 1];
int minRight2 = partition2 == n
? int.MaxValue
: nums2[partition2];
if (maxLeft1 <= minRight2 &&
maxLeft2 <= minRight1)
{
if (total % 2 == 1)
{
return Math.Max(maxLeft1, maxLeft2);
}
return (
Math.Max(maxLeft1, maxLeft2) +
Math.Min(minRight1, minRight2)
) / 2.0;
}
if (maxLeft1 > minRight2)
{
right = partition1 - 1;
}
else
{
left = partition1 + 1;
}
}
return 0;
}
}Code Walkthrough
1. Search the Smaller Array
The first check ensures that nums1 is the smaller array. This is important because binary search should operate over the smallest possible search space.
2. Calculate the Second Partition
Once partition1 is chosen, partition2 is determined automatically. This means we only need to binary search one partition instead of searching two independently.
3. Check the Four Boundary Values
The four values around the partitions tell us whether the split is valid:
maxLeft1 <= minRight2
maxLeft2 <= minRight14. Move the Binary Search
If maxLeft1 > minRight2, too many elements were taken from nums1, so the partition moves left.
Otherwise, the partition moves right.
5. Calculate the Median
Once the partition is valid, the median can be obtained directly from the largest value on the left and the smallest value on the right. No merged array is required.
Complexity Analysis
Time: O(log min(m, n)) because binary search is performed only on the smaller array.
Space: O(1) because the algorithm uses only a fixed number of variables and does not create a merged array.
Edge Cases
- One array is empty: The partition logic handles this using infinity boundary values.
- Both arrays contain duplicate values: The comparison uses less-than-or-equal, so duplicates are handled correctly.
- Total number of elements is odd: The median is the largest value on the left side.
- Total number of elements is even: The median is the average of the largest left value and smallest right value.
- One array is much smaller than the other: Binary search is performed on the smaller array to keep the search space minimal.
Common Mistakes and Tips
- Do not merge the arrays if the goal is to satisfy the logarithmic runtime requirement.
- Always binary search the smaller array.
- Remember that a partition can be at index 0 or at the end of an array.
- For an even number of elements, use floating-point division when calculating the average.
FAQ
Why do we binary search the smaller array?
Searching the smaller array minimizes the number of possible partition positions. This gives O(log min(m,n)) time.
Why don't we merge the two arrays?
Merging requires O(m + n) time. The problem specifically requires logarithmic runtime, so the solution must use the sorted structure of the arrays instead.
Why are Infinity values used?
A partition can occur at the beginning or end of an array, meaning one side has no actual boundary element. Negative and positive infinity allow those cases to be handled with the same comparison logic.
Related Problems
- LeetCode 33 — Search in Rotated Sorted Array
- LeetCode 35 — Search Insert Position
- LeetCode 153 — Find Minimum in Rotated Sorted Array
- LeetCode 162 — Find Peak Element
Conclusion
The main lesson from the LeetCode 4 Median of Two Sorted Arrays solution is to stop thinking about merging and instead think about finding the correct partition. Because both arrays are already sorted, only four boundary values are needed to determine whether a partition is valid.
Binary searching the partition in the smaller array reduces the search to O(log min(m,n)) time while using O(1) extra space. This partition technique is a useful pattern to remember for problems where sorted collections need to be combined conceptually without actually merging them.
