All problems

Asteroid Collision

Medium · stack

A row of asteroids drifts through space along a line. You are given a list asteroids of non-zero integers. For each asteroid, the absolute value is its size, and the sign is its direction: a positive value moves to the right and a negative value moves to the left. All asteroids move at the same speed.

Two asteroids collide when one that moves right is directly to the left of one that moves left, with nothing in between. When they collide, the smaller one explodes. If both have the same size, both explode. The bigger asteroid carries on in the same direction and may go on to collide with the next one. Asteroids moving in the same direction never meet, and asteroids that move apart never meet either.

Keep going until no more collisions can happen, and return the asteroids that are left, in their original left-to-right order. If every asteroid explodes, return an empty list.

Examples

Example 1

Input: asteroids = [4, 2, -3]

Output: [4]

The 2 meets the -3 and explodes. Then the 4 meets the -3, which is smaller, so the -3 explodes.

Example 2

Input: asteroids = [5, -5, -2, 3]

Output: [-2, 3]

The 5 and -5 are the same size, so both explode. The -2 moves left and the 3 moves right, so they never meet.

Example 3

Input: asteroids = [-1, -2, 3, 4]

Output: [-1, -2, 3, 4]

The left movers are on the left and the right movers are on the right, so nothing collides.

Constraints