Median of Two Sorted Arrays
Problem
Given two individually sorted arrays of sizes m and n, return the median of all their elements combined. The overall run time must be O(log(m + n)), so merging the arrays is not allowed.
Examples
Constraints
- • 0 <= m, n <= 1000
- • 1 <= m + n <= 2000
- • Both arrays are sorted ascending
Hints & approach
Hint 1
The median splits the combined data into a left half and a right half of equal size.
Hint 2
If you choose how many elements the left half takes from nums1, the count from nums2 is forced.
Hint 3
Binary search that cut in the shorter array until every left value is <= every right value.
Approachtry the hints first
Binary search a partition index i in the shorter array A; the partner index in B is j = (m + n + 1) / 2 - i, so the left side always holds half the elements. The partition is valid when A[i-1] <= B[j] and B[j-1] <= A[i] (treat out-of-range as -infinity / +infinity). If A[i-1] is too big, move i left; if B[j-1] is too big, move i right. Once valid, the median is max(A[i-1], B[j-1]) for an odd total, or the average of that and min(A[i], B[j]) for an even total. Searching only the shorter array gives O(log min(m, n)).
Time O(log min(m, n)) · Space O(1)