Median of Two Sorted Arrays
HardBinary search the partition
Cut both sorted lists so the left halves hold exactly half the numbers; the middle values give the median.
The idea
Partition the smaller array so the combined left half has (m+n+1)/2 elements and every left value ≤ every right value. Binary search that cut.
a[1,2]
b[3,4]
Step 1 of 6. Brute force: merge both sorted arrays, then read off the middle value. a [1,2], b [3,4].
1/6
Brute force
timeO(m+n)spaceO(m+n)
Merge then pick.
1const merged = [];2while (i < a.length || j < b.length) merged.push(takeSmaller());3return median(merged);Memory
- last
- —
- a
- [1,2]
- b
- [3,4]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = [1, 3], b = [2]
- Output:
- 2
- Explanation:
- Merged 1,2,3 → median 2.
Example 2
- Input:
- a = [1, 2], b = [3, 4]
- Output:
- 2.5
- Explanation:
- Middle two are 2 and 3 → 2.5.
Example 3
- Input:
- a = [0, 0], b = [0, 0]
- Output:
- 0.0
- Explanation:
- All zeros → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.