0739HardArrayDynamic ProgrammingStackSortingMonotonic StackOrdered Set

Sound Launch Stations On A Relay Pipeline

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.

A pipeline carries pressure gauges at stations 0 through n - 1, and readings[i] is the gauge value at station i. A message can be relayed forward from station to station, always to a station with a larger index. The relays a message makes are numbered 1, 2, 3, and so on in the order they happen, and the numbering decides where each relay is allowed to land.

Suppose the message currently sits at station i.

On an odd-numbered relay, look at every station j > i whose reading is greater than or equal to readings[i]. Among those, the message must go to a station holding the smallest such reading. If two or more stations hold that smallest reading, it goes to the one with the smallest index.
On an even-numbered relay, look at every station j > i whose reading is less than or equal to readings[i]. Among those, the message must go to a station holding the largest such reading. If two or more stations hold that largest reading, it goes to the one with the smallest index.

If no station ahead of i qualifies for the relay that is due, the message can go no further and is stuck at station i.

Call station s a sound launch station when a message released at s reaches station n - 1 after some number of relays. Station n - 1 is sound because a message released there is already at the end.

Return how many of the n stations are sound launch stations.

Examples

Example 1

Input: readings = [7, 7, 3, 9, 7]
Output: 4

From station 0 the first relay is odd: stations 1, 3 and 4 hold 7, 9 and 7, the smallest qualifying reading is 7, and station 1 is the earlier of the two stations holding it. The second relay is even and station 4 holds 7, so the message lands on the last station. Stations 1, 2 and 4 also finish at station 4. A message released at station 3 needs a reading of at least 9 ahead of it and station 4 holds 7, so it is stuck.

Example 2

Input: readings = [24, 6, 24, 40]
Output: 2

A message released at station 2 relays to station 3, whose reading of 40 is the smallest one at least 24 ahead of it, and station 3 is the last station. Station 3 itself is sound. A message released at station 0 relays to station 2, then needs a reading of at most 24 ahead of station 2 and only 40 remains, so it is stuck; the message released at station 1 ends up stuck at station 2 in the same way.

Example 3

Input: readings = [83, 61, 40, 22]
Output: 1

Every station ahead of any other holds a smaller reading, so the odd first relay never has a qualifying destination and a message stays where it is released. Only station 3, which is already the last station, is sound.

Constraints

1 <= readings.length <= 2 * 10^4
0 <= readings[i] <= 10^5 - 1

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 sound_launch_stations(readings: list[int]) -> int:

Java

public int soundLaunchStations(int[] readings)

The intended approach

Time O(n log n): two sorts of the indices, then linear stack and sweep passes.Space O(n) for the destination arrays, the stack and the two flag arrays.

Each station has at most one legal destination for an odd relay and at most one for an even relay, so precompute both. Walk the station indices in increasing order of `(reading, index)` and keep a stack of indices seen but not yet resolved: when the current index is larger than the index on top of the stack, that stacked station's odd destination is the current one, so pop and record it. Because equal readings are visited earliest-index-first, the tie lands on the smallest index. Repeating the same sweep over `(-reading, index)` gives every even destination. Then sweep stations from the last one backwards, keeping two flags per station: a message here whose next relay is odd is sound when the odd destination exists and is sound with an even relay next, and symmetrically. Both flags are true at the final station. The answer counts the stations whose odd flag is set, since the first relay is always odd.

Pythonentry point: sound_launch_stations

def sound_launch_stations(readings):
    # For each station work out the two possible relay targets once, using a
    # monotonic stack walked in value order, then sweep the stations from the
    # back deciding soundness for an odd relay and for an even relay.
    # O(n log n) time (two sorts), O(n) space.
    n = len(readings)
    if n == 1:
        return 1

    def targets(order):
        """For each index, the next index after it in the sequence `order`."""
        res = [-1] * n
        stack = []
        for i in order:
            while stack and i > stack[-1]:
                res[stack.pop()] = i
            stack.append(i)
        return res

    # smallest reading that is >= this one, earliest such station on a tie
    up = targets(sorted(range(n), key=lambda i: (readings[i], i)))
    # largest reading that is <= this one, earliest such station on a tie
    down = targets(sorted(range(n), key=lambda i: (-readings[i], i)))

    odd = [False] * n
    even = [False] * n
    odd[n - 1] = True
    even[n - 1] = True
    for i in range(n - 2, -1, -1):
        if up[i] != -1:
            odd[i] = even[up[i]]
        if down[i] != -1:
            even[i] = odd[down[i]]
    return sum(1 for i in range(n) if odd[i])

The obvious version

Release a message from every station and follow its chain step by step, rescanning all stations ahead to choose each destination directly from the rules. Cubic in the worst case, with no precomputation and no ordering trick.

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_sound_launch_stations(readings):
    """Launch from every station in turn and follow the relay chain literally,
    rescanning the whole tail of the pipeline to pick each destination."""
    n = len(readings)
    total = 0
    for start in range(n):
        here = start
        step = 1
        while here != n - 1:
            cur = readings[here]
            pick = -1
            best = None
            for j in range(here + 1, n):
                v = readings[j]
                if step % 2 == 1:
                    if v >= cur and (best is None or v < best):
                        best, pick = v, j
                else:
                    if v <= cur and (best is None or v > best):
                        best, pick = v, j
            if pick < 0:
                break
            here = pick
            step += 1
        if here == n - 1:
            total += 1
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 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