Median of Two Sorted Arrays
Real-world version: Paired Station MedianThe statement here is our own: the same inputs, outputs and technique.
Two weather stations each keep a log of temperature readings in whole degrees, and each log already runs from coldest to warmest. north holds one station's log, south holds the other's. A reading may repeat inside a log, readings may fall below zero, and one of the two logs may hold nothing at all, though not both at once.
Picture every reading from both logs poured into one shared line-up, still ordered coldest to warmest. Return the value standing at the centre of that line-up, as a decimal. When the shared line-up holds an even count there are two values at the centre, and the answer is their mean.
Pouring the two logs together is off limits, and so is ordering them again. Instead, settle the answer by halving the range of candidate cut points inside the shorter log, so the work grows with the logarithm of the shorter log's length.
Examples
Example 1
- Input
- north = [1, 2, 3], south = [10]
- Output
- 2.5
The shared line-up reads 1, 2, 3, 10. Four readings put two of them at the centre, 2 and 3, whose mean is 2.5.
Example 2
- Input
- north = [5, 6], south = [-3, -2, -1]
- Output
- -1.0
The shared line-up reads -3, -2, -1, 5, 6. Five readings leave a single centre, the third one.
Example 3
- Input
- north = [], south = [2, 4, 6]
- Output
- 4.0
One station reported nothing, so the other log is the whole line-up and its middle reading answers on its own.
Constraints
- north.length == m
- south.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= north[i], south[i] <= 10^6
- Both logs are given in non-decreasing order
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def paired_station_median(north: list[int], south: list[int]) -> float:public double pairedStationMedian(int[] north, int[] south)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's