Median of Two Sorted Arrays
You're given two sorted integer arrays nums1 and nums2 of lengths m and n. Return the median of all m + n values combined. When the total count is even, the median is the average of the two middle values. Your solution must run in O(log(m + n)) time. Either array may be empty, but not both.
Examples
nums1 = [2,7], nums2 = [5] returns 5.0
Merged, the values are [2,5,7], and the middle one is 5.
nums1 = [1,6], nums2 = [3,8] returns 4.5
Merged, the values are [1,3,6,8]. The two middle values are 3 and 6, and their average is 4.5.
nums1 = [], nums2 = [4,9] returns 6.5
With one array empty, the median comes from the other array alone.
Constraints
- 0 <= m, n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
Hints
Merging the arrays takes O(m + n). The median only needs to know where the dividing line between the smaller and larger halves falls.
Pick how many elements of nums1 go in the left half; that fixes how many come from nums2. Binary search that count.
Search i in [0, m] on the shorter array, with j = (m + n + 1) / 2 - i. Compare nums1[i - 1] with nums2[j] and nums2[j - 1] with nums1[i], using infinities at the edges, and move i until both checks pass.
Drill This: Your Approach First
Approach
Split both arrays so the left halves together hold half of all values, rounded up, and every value on the left is no greater than every value on the right. Binary search the cut i in the shorter array; the cut in the longer one is then j = half - i. The split is correct when nums1[i - 1] <= nums2[j] and nums2[j - 1] <= nums1[i], treating missing neighbors as minus and plus infinity. If nums1[i - 1] is too large, move i left; otherwise move it right. The median is the largest left value for an odd total, or its average with the smallest right value for an even total. O(log(min(m, n))) time, O(1) space.
Time
O(log(min(m, n)))
Space
O(1)
Pitfall
Solutions
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
int m = nums1.length, n = nums2.length;
int half = (m + n + 1) / 2;
int lo = 0, hi = m;
while (lo <= hi) {
int i = (lo + hi) / 2;
int j = half - i;
int left1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int right1 = i == m ? Integer.MAX_VALUE : nums1[i];
int left2 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int right2 = j == n ? Integer.MAX_VALUE : nums2[j];
if (left1 <= right2 && left2 <= right1) {
int leftMax = Math.max(left1, left2);
if ((m + n) % 2 == 1) return leftMax;
return (leftMax + (double) Math.min(right1, right2)) / 2.0;
} else if (left1 > right2) {
hi = i - 1;
} else {
lo = i + 1;
}
}
throw new IllegalArgumentException("Inputs must be sorted");
}
}class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2
lo, hi = 0, m
inf = float("inf")
while lo <= hi:
i = (lo + hi) // 2
j = half - i
left1 = nums1[i - 1] if i > 0 else -inf
right1 = nums1[i] if i < m else inf
left2 = nums2[j - 1] if j > 0 else -inf
right2 = nums2[j] if j < n else inf
if left1 <= right2 and left2 <= right1:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return float(left_max)
return (left_max + min(right1, right2)) / 2
if left1 > right2:
hi = i - 1
else:
lo = i + 1
raise ValueError("Inputs must be sorted")