Show problems as
Classic problem #735MediumArrayStackSimulation

Asteroid Collision

Real-world version: Single Rail Sled Run
Tracked in this browser only
Read Asteroid Collision on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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

Python
def surviving_sleds(sleds: list[int]) -> list[int]:
Java
public int[] survivingSleds(int[] sleds)

More on the same topics