0080MediumArrayStackSimulation

Single Rail Sled Run

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 test facility releases cargo sleds onto one straight rail at the same instant. sleds lists them in rail order, from the west end toward the east end. Each entry is non-zero: its magnitude is the sled's mass and its sign is its heading, positive for a sled rolling east and negative for one rolling west.

Every sled runs at the same speed, so two sleds heading the same way never close on each other, and a westbound sled never catches anything already west of it. A meeting therefore only happens when an eastbound sled has a westbound sled somewhere east of it with nothing left between them.

When two sleds meet, the lighter one is knocked off the rail and the heavier one rolls on unchanged, still at the same mass and heading. If the two masses are equal, both are knocked off. A sled with nothing left to meet keeps rolling forever.

Return the signed masses of the sleds still on the rail once no further meetings can happen, in rail order from west to east.

Examples

Example 1

Input: sleds = [4, 9, -4]
Output: [4, 9]

The westbound sled of mass 4 runs into the eastbound sled of mass 9 and loses; the leading sled of mass 4 is never caught because the two survivors both head east.

Example 2

Input: sleds = [6, -6]
Output: []

The two sleds meet head on carrying the same mass, so the rail clears completely.

Example 3

Input: sleds = [12, 3, -7]
Output: [12]

The westbound sled removes the eastbound sled of mass 3, then meets the sled of mass 12 and is removed itself.

Example 4

Input: sleds = [-3, -1, 2, 5]
Output: [-3, -1, 2, 5]

Both westbound sleds sit west of both eastbound sleds, so the four spread apart and nothing ever meets.

Constraints

2 <= sleds.length <= 10^4
-1000 <= sleds[i] <= 1000
sleds[i] != 0

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 surviving_sleds(sleds: list[int]) -> list[int]:

Java

public int[] survivingSleds(int[] sleds)

The intended approach

Time O(n)Space O(n)

Sweep west to east keeping a stack of the sleds that are still in play. An eastbound sled is just pushed; a westbound sled fights the stack top while that top is eastbound, popping tops it outweighs, and stopping either because it lost or because it tied and both went off. Only a sled that survives every fight gets pushed, so each sled is pushed and popped at most once.

Pythonentry point: surviving_sleds

def surviving_sleds(sleds):
    rail = []
    for sled in sleds:
        rolling = True
        while rolling and rail and rail[-1] > 0 and sled < 0:
            if rail[-1] < -sled:
                rail.pop()
            elif rail[-1] == -sled:
                rail.pop()
                rolling = False
            else:
                rolling = False
        if rolling:
            rail.append(sled)
    return rail

The obvious version

Simulate literally: scan the rail for the westmost adjacent eastbound-then-westbound pair, resolve just that meeting, and restart the scan. Repeat until no such pair is left. O(n^2).

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_surviving_sleds(sleds):
    rail = list(sleds)
    settled = False
    while not settled:
        settled = True
        for i in range(len(rail) - 1):
            if rail[i] > 0 and rail[i + 1] < 0:
                east = rail[i]
                west = -rail[i + 1]
                if east < west:
                    rail.pop(i)
                elif east > west:
                    rail.pop(i + 1)
                else:
                    rail.pop(i + 1)
                    rail.pop(i)
                settled = False
                break
    return rail

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
4 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