Median of Two Sorted Arrays
Maintained by Vikas D, software engineer
You are handed two arrays, nums1 and nums2. Each one is sorted in non-decreasing order on its own, but they are kept separate. Picture them merged into a single sorted list of every value from both. The median is the middle of that combined list.
When the combined length is odd, the median is the single middle value. When it is even, the median is the average of the two middle values, so the answer can be a fraction even when every input value is an integer.
The catch is the time budget. A naive merge runs in linear time, but the target is O(log(m+n)). That rules out walking through the elements and forces you to reason about where the median sits without ever building the merged list.
Either array may be empty, but their combined length is at least one, so a median always exists.
Examples
Combined and sorted the values are [1,2,3]. Three elements means one middle value, which is 2.
Combined the values are [1,2,3,4]. Four elements means the median is the average of the two middle values, (2 + 3) / 2 = 2.5.
One array is empty, so the merged list is just [1] and the only element is the median.
Merged the values are [1,2,3,4,5,6]. With six elements the median averages the two middle values, (3 + 4) / 2 = 3.5.
Constraints
- 0 <= nums1.length, nums2.length <= 1000
- nums1.length + nums2.length >= 1
- -10^6 <= nums1[i], nums2[i] <= 10^6
- Both arrays are sorted in non-decreasing order
- Overall run time must be O(log(m+n))
Visible test cases
- findMedianSortedArrays([1,3], [2]) == 2
- findMedianSortedArrays([1,2], [3,4]) == 2.5
- findMedianSortedArrays([], [1]) == 1
- findMedianSortedArrays([2], []) == 2
- findMedianSortedArrays([1,3,5], [2,4,6]) == 3.5
- findMedianSortedArrays([1,2,3,4,5], [6,7,8,9,10]) == 5.5
Hints
Hint 1
The median splits the combined data into a left half and a right half of equal size, where every value on the left is no larger than every value on the right. You do not need the actual sorted order, only that split point.
Hint 2
Once you decide how many elements of nums1 fall into the left half, the count taken from nums2 is forced, because the two halves together must hold a fixed number of elements. So you are really searching for one number: how many elements to take from the shorter array.
Hint 3
Binary search that single number. For a candidate split, look at the largest value on the left of each array and the smallest value on the right of each array. The split is correct when both arrays' left maxima are no greater than both arrays' right minima.
Approaches
Merge then pick the middle
Time O(m + n) · Space O(m + n)Build the fully merged sorted sequence, then read the median straight out of the middle position.
- Walk two pointers across nums1 and nums2, always taking the smaller current value, to produce one merged sorted array.
- Let total be the combined length.
- If total is odd, return the element at index total / 2 (integer division).
- If total is even, return the average of the elements at indices total / 2 - 1 and total / 2.
- You can stop merging early once you pass the middle index, but the worst case still touches every element.
Binary search the partition
Time O(log(min(m, n))) · Space O(1)Find a cut that divides the two arrays into a left group and a right group of equal size such that everything on the left is no larger than everything on the right. Binary search the cut position in the shorter array only.
- Always binary search the shorter array so the search range stays small; swap the inputs if nums1 is longer.
- Let half = (m + n + 1) / 2, the number of elements that belong to the left side.
- Binary search i, the count taken from nums1, in the range 0 to m. The count taken from nums2 is then j = half - i.
- Define left1, right1 as the values just before and at the cut in nums1 (use negative and positive infinity at the boundaries), and left2, right2 likewise for nums2.
- If left1 <= right2 and left2 <= right1, the cut is valid: when the total is odd return max(left1, left2), otherwise return the average of max(left1, left2) and min(right1, right2).
- If left1 > right2 the cut took too much from nums1, so move the upper bound down; otherwise move the lower bound up, and repeat.
Common mistakes
- Forgetting the even case returns a fraction. Even with all-integer inputs the answer can be a value like 2.5, so use floating-point division, not integer division.
- Mishandling an empty array. When one array has length zero the binary search must still run cleanly, which is why the boundary sentinels (negative and positive infinity) matter.
- Binary searching the longer array. If you do not swap so the search is over the shorter array, the derived index j = half - i can fall outside the other array's bounds.
- Using half = (m + n) / 2 instead of (m + n + 1) / 2. The +1 makes the odd-length median land on the left side, so max(left1, left2) is the answer and the same formula works for both parities.
- Off-by-one on the left or right values at the cut. left is the element just before the cut index, right is the element at the cut index; mixing these up gives a wrong but plausible-looking result.
Follow-up variations
- What changes if the arrays are not guaranteed sorted? You would sort first, which makes the merge approach O((m+n) log(m+n)) and removes the O(log) option.
- Generalise to finding the k-th smallest element across the two arrays instead of just the median.
- Extend to the median across more than two sorted arrays, or across a stream where new values keep arriving.
- How would you return both middle indices, not just the median value, for an even total?