Given two sorted arrays nums1 and nums2 of sizes m and n respectively, find the median of the combined sorted array. The overall run time complexity should be O(log(min(m, n))).
For example, given nums1 = [1, 3] and nums2 = [2], the merged array is [1, 2, 3] and the median is 2.0. Given nums1 = [1, 2] and nums2 = [3, 4], the merged array is [1, 2, 3, 4] and the median is 2.5.
Explain your approach, why binary search works here, how you partition the arrays, and analyze complexity.
How to approach it
- Hint 1
The median divides the combined array into two equal halves. You need to find the correct partition without merging.
- Hint 2
Binary search on the shorter array to find how many elements from each array go into the left half.
- Hint 3
If you take i elements from nums1, you must take (m + n + 1) / 2 - i elements from nums2 for the left half. Check that the partition is valid by comparing boundary elements.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.