You are given two sorted arrays nums1 and nums2 of sizes m and n. Return the median of all m + n numbers taken together. The overall run time should be O(log(m + n)).
- 0 <= m, n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Merging both arrays (or walking two pointers to the middle) is O(m + n). For O(log) we think about a partition: cut A after i elements and B after j elements, with i + j = (m + n + 1) / 2, so the left side holds half the numbers. The partition is correct when every left value is at most every right value, which (since each array is sorted) only needs A[i-1] <= B[j] and B[j-1] <= A[i]. If A[i-1] > B[j], we took too many from A, so move i left; otherwise move it right. Binary searching i over the shorter array gives O(log(min(m, n))). The median is then the largest left value (odd total) or the average of the largest left and smallest right values (even total).
Algorithm
- Make
Athe shorter array. Lethalf = (m + n + 1) / 2and searchiin[0, m]. - Set
j = half - i. ReadaLeft = A[i-1],aRight = A[i],bLeft = B[j-1],bRight = B[j], using minus infinity and plus infinity when an index is out of range. - If
aLeft <= bRightandbLeft <= aRight, the partition is correct. - If
aLeft > bRight, sethi = i - 1; otherwise setlo = i + 1. - At the correct partition: if
m + nis odd returnmax(aLeft, bLeft), else return(max(aLeft, bLeft) + min(aRight, bRight)) / 2.
O(log(min(m, n)))Space: O(1)j = half - i can go negative or past the end of the other array, causing index errors. Also divide by 2.0, not 2, to keep the fraction.class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: a, b = nums1, nums2 if len(a) > len(b): a, b = b, a # binary search the shorter array m, n = len(a), len(b) half = (m + n + 1) // 2 # size of the left part lo, hi = 0, m while lo <= hi: i = (lo + hi) // 2 # elements taken from a j = half - i # elements taken from b a_left = a[i - 1] if i > 0 else float('-inf') a_right = a[i] if i < m else float('inf') b_left = b[j - 1] if j > 0 else float('-inf') b_right = b[j] if j < n else float('inf') if a_left <= b_right and b_left <= a_right: left_max = max(a_left, b_left) if (m + n) % 2 == 1: return float(left_max) return (left_max + min(a_right, b_right)) / 2.0 elif a_left > b_right: hi = i - 1 # took too many from a else: lo = i + 1 # took too few from a return 0.0