Why it works
- The median splits all the numbers into two halves where every left number is at most every right one. If i numbers come from a, the other half − i must come from b, so the cut in a alone decides the split.
- Each array is sorted, so only two pairs can be out of order: a[i − 1] with b[j] and b[j − 1] with a[i]. If a[i − 1] > b[j], too many come from a and the cut moves left; if b[j − 1] > a[i], too few, and it moves right. That is a binary search over i.
- Searching over the shorter array keeps j between 0 and len(b). Here it takes three cuts: 2 is too few, 4 too many, 3 is right.
Complexity
Time O(log(min(m, n))): binary search over the cut in the shorter array. Memory O(1): the arrays are never merged.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗