0020HardArrayBinary SearchDivide and Conquer

Paired Station Median

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def paired_station_median(north: list[int], south: list[int]) -> float:

Java

public double pairedStationMedian(int[] north, int[] south)

The intended approach

Time O(log(min(m, n)))Space O(1)

The answer only depends on where the shared line-up splits into a colder half and a warmer half of the right sizes. Cut the shorter log after `take` readings; the cut in the longer log is then forced, because the two halves must hold a fixed number of readings between them. The cut is the right one exactly when the last reading on each cold side is no warmer than the first reading on the opposite warm side; if the shorter log contributed something too warm, move its cut left, otherwise move it right. Binary searching `take` over 0 through the shorter length settles it, with sentinels of minus and plus infinity standing in for a side that ran out, which is also what makes an empty log fall out for free.

Pythonentry point: paired_station_median

def paired_station_median(north, south):
    small, big = north, south
    if len(small) > len(big):
        small, big = big, small
    m, n = len(small), len(big)
    total = m + n
    cold_side = (total + 1) // 2
    coldest = float("-inf")
    warmest = float("inf")
    low, high = 0, m
    while low <= high:
        take = (low + high) // 2
        rest = cold_side - take
        small_cold = small[take - 1] if take > 0 else coldest
        small_warm = small[take] if take < m else warmest
        big_cold = big[rest - 1] if rest > 0 else coldest
        big_warm = big[rest] if rest < n else warmest
        if small_cold <= big_warm and big_cold <= small_warm:
            centre_cold = max(small_cold, big_cold)
            if total % 2 == 1:
                return float(centre_cold)
            centre_warm = min(small_warm, big_warm)
            return (centre_cold + centre_warm) / 2.0
        if small_cold > big_warm:
            high = take - 1
        else:
            low = take + 1
    return 0.0

The obvious version

Pour both logs into one list, order it, and index the centre directly, O((m + n) log(m + n)).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_paired_station_median(north, south):
    pooled = sorted(list(north) + list(south))
    count = len(pooled)
    if count % 2 == 1:
        return float(pooled[count // 2])
    return (pooled[count // 2 - 1] + pooled[count // 2]) / 2.0

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in