Two-Station Median
A mountain rescue team has two weather stations, one on the north ridge and one on the south ridge. Each night, each station logs temperature readings in whole degrees and keeps them sorted from coldest to warmest. The two stations do not always log the same number of readings.
The team's morning report uses the median of all readings from both stations together: the middle value, or the average of the two middle values when the total count is even. The base asks a station for one reading at a time, by position, over a slow radio link, so you want to find the median by asking for only a few readings, not by pulling in everything and merging it.
Your task
Write medianReading(north, south). Both lists are sorted in non-decreasing order. Return the median of all readings from both lists combined, as a number. If the combined count is even, return the average of the two middle values (which may end in .5).
At least one list is non-empty. Aim for O(log(min(m, n))), where m and n are the two lengths.
medianReading(north: int[], south: int[]) → float Numbers are accepted within 1e-6.
Examples
north = [-3, 1, 4] south = [-1, 2]
1
All five readings in order: -3, -1, 1, 2, 4. The middle one is 1.
north = [2, 6] south = [3, 9]
4.5
In order: 2, 3, 6, 9. Four readings, so average the middle two: (3 + 6) / 2 = 4.5.
north = [1, 2, 3] south = [10, 11, 12, 13]
10
In order: 1, 2, 3, 10, 11, 12, 13. The middle (4th) reading is 10, from the south list. The whole north list sits below the median.
Constraints
- 0 ≤ north.length, south.length ≤ 10,000
- 1 ≤ north.length + south.length
- -50 ≤ each reading ≤ 50
- Answers within 0.000001 of the expected value are accepted.
Start with brute force
Merge the two sorted lists into one, as in merge sort, and read off the middle. That is O(m + n), and you can stop the merge halfway, but it is still linear.
Linear is fine for 20,000 readings on a fast machine. The point of this problem is the harder question: you only need to know where the middle cut falls, and that can be found with a binary search over the shorter list, about 14 peeks for 10,000 readings.
Hints
0 of 4 shown- Hint 1
In the first example the combined list has 5 readings, so 3 of them are on the "low side" of the median. If 1 of those 3 comes from the south list, how many must come from the north list?
- Hint 2
The low side always holds
half = floor((m + n + 1) / 2)readings. If you takeifrom the start of one list, you must takehalf - ifrom the other. So the whole split is decided by one number,i. - Hint 3
A split is correct when nothing on the low side is bigger than anything on the high side. Since each list is sorted, you only need to check across the cut: the last low reading of each list against the first high reading of the other. If one check fails, it tells you whether
iis too big or too small. - Hint 4
Binary search
iover the shorter list, from 0 to its length. Withj = half - i, comparea[i-1]withb[j]andb[j-1]witha[i](treat a missing value as -∞ on the left, +∞ on the right). When both hold, the median is the largest low value (odd total) or the average of the largest low and the smallest high value (even total).
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Think of the median as a cut through both lists at once. The low side takes the first i readings of one list and the first j of the other, with i + j = half. The cut is right exactly when every low reading is ≤ every high reading. Because both lists are sorted, that boils down to two cross checks at the cut.
Trace the third example. The shorter list is a = [1, 2, 3], b = [10, 11, 12, 13]. Total 7, so half = 4, and i can be 0 to 3:
lo = 0,hi = 3,i = 1,j = 3. Low side: 1 from a, 10, 11, 12 from b. Check: is b's last low (12) ≤ a's first high (2)? No. The low side has too much of b, so take more from a:lo = 2.i = 2,j = 2. b's last low is 11, a's first high is 3. Still too much of b:lo = 3.i = 3,j = 1. a's last low is 3 ≤ b's first high 11. b's last low is 10 ≤ a's first high, which is +∞ because a is used up. Both checks pass.- The total is odd, so the median is the largest low value: max(3, 10) = 10.
Searching over the shorter list matters: it keeps j = half - i between 0 and n, so the index into the longer list is always valid. The ±∞ stand-ins handle cuts at the very start or end of a list, including an empty list.
function medianReading(north, south) {
// search over the shorter list
const [a, b] = north.length <= south.length ? [north, south] : [south, north];
const m = a.length, n = b.length;
const half = Math.floor((m + n + 1) / 2); // size of the low side
let lo = 0, hi = m;
while (true) {
const i = Math.floor((lo + hi) / 2); // take i from a, half - i from b
const j = half - i;
const aLow = i > 0 ? a[i - 1] : -Infinity, aHigh = i < m ? a[i] : Infinity;
const bLow = j > 0 ? b[j - 1] : -Infinity, bHigh = j < n ? b[j] : Infinity;
if (aLow > bHigh) hi = i - 1; // took too many from a
else if (bLow > aHigh) lo = i + 1; // took too few from a
else {
const lowMax = Math.max(aLow, bLow);
if ((m + n) % 2 === 1) return lowMax;
return (lowMax + Math.min(aHigh, bHigh)) / 2;
}
}
}def median_reading(north, south):
# search over the shorter list
a, b = (north, south) if len(north) <= len(south) else (south, north)
m, n = len(a), len(b)
half = (m + n + 1) // 2 # size of the low side
inf = float('inf')
lo, hi = 0, m
while True:
i = (lo + hi) // 2 # take i from a, half - i from b
j = half - i
a_low = a[i - 1] if i > 0 else -inf
a_high = a[i] if i < m else inf
b_low = b[j - 1] if j > 0 else -inf
b_high = b[j] if j < n else inf
if a_low > b_high:
hi = i - 1 # took too many from a
elif b_low > a_high:
lo = i + 1 # took too few from a
else:
low_max = max(a_low, b_low)
if (m + n) % 2 == 1:
return float(low_max)
return (low_max + min(a_high, b_high)) / 2Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.