Coding Interview PatternsMedian of Two Sorted Arrays
HardModified Binary Search
Median of Two Sorted Arrays
Explanation & Solution
Description
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log(m + n)).
Input:nums1 = [1, 3], nums2 = [2]
0
1
1
3
0
2
Output: 2
Explanation: Merged array = [1, 2, 3] and median is 2.
Constraints
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
Approach
Modified Binary Search pattern
1. Ensure Binary Search on the Smaller Array
- If
nums1is longer thannums2, swap them. This ensures O(log(min(m, n))).
2. Binary Search on Partition Point
- Search for partition index
iinnums1(from 0 to m). - Compute
j = (m + n + 1) / 2 - ifornums2. - The partition divides both arrays such that the left half has
(m + n + 1) / 2elements total.
3. Check Partition Validity
- Define boundary values:
left1,right1,left2,right2(use ±∞ for out-of-bounds). - Valid partition:
left1 <= right2ANDleft2 <= right1. - If
left1 > right2, move partition left:hi = i - 1. - If
left2 > right1, move partition right:lo = i + 1.
4. Compute the Median
- Odd total: median =
max(left1, left2). - Even total: median =
(max(left1, left2) + min(right1, right2)) / 2.
🧠 Key Insight
- The insight is partitioning both arrays simultaneously: by choosing where to split the smaller array, the split point in the larger array is determined. A valid partition means all elements on the left are ≤ all elements on the right.
Time
O(log(min(m, n))) — binary search on the shorter array.Space
O(1).Visualization
Input:
[1, 3]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
6 steps