Median of Two Sorted Feeds
HardBinary Search
Problem
Two price feeds each deliver their quotes as an array sorted in non-decreasing order: a and b. Return the median of all the quotes combined.
With an even total, the median is the mean of the two middle values. Your algorithm must run in O(log(min(m, n))) time.
Example 1
- Input:
- a = [1, 4, 9], b = [2, 3]
- Output:
- 3.0
Merged: [1, 2, 3, 4, 9]; the middle value is 3.
Example 2
- Input:
- a = [1, 2], b = [5, 6]
- Output:
- 3.5
Merged: [1, 2, 5, 6]; (2 + 5) / 2 = 3.5.
Example 3
- Input:
- a = [], b = [7]
- Output:
- 7.0
Constraints
- 0 ≤ a.length, b.length ≤ 10^5
- 1 ≤ a.length + b.length
- -10^6 ≤ a[i], b[i] ≤ 10^6
Hint
Show the first hint
The median splits the merged list into a left half and a right half of equal size. How would that split look in each of a and b?
Walkthrough
How to approach it
01Clarify before coding
- Can one array be empty? Yes, but not both.
- Even total: mean of the two middle values? Yes, so the result is a float.
- Is merging acceptable? It is O(m + n); the requirement is logarithmic.
02Brute force
Merge the arrays with two pointers (stopping at the middle) and read the median.
Cost: O(m + n) time, O(1) space if you only walk to the middle. Correct, but linear.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.