Asteroid collision: resolve moving asteroids with a stack

Asteroids move along a line. Each is an integer: its absolute value is its size, and its sign is its direction (positive moves right, negative moves left). All move at the same speed, so only a right-mover followed by a left-mover can meet. When two meet, the smaller explodes; if they are the same size, both explode. Return the asteroids left after every collision, in their original order.

Interface

Unless you agree on a different interface with the interviewer, assume:

• asteroid_collision(asteroids: list[int]) -> list[int]

Example

asteroid_collision([5, 10, -5])      ->  [5, 10]
asteroid_collision([8, -8])          ->  []
asteroid_collision([10, 2, -5])      ->  [10]           # -5 destroys 2, then loses to 10
asteroid_collision([-2, -1, 1, 2])   ->  [-2, -1, 1, 2] # moving apart
asteroid_collision([1, -2, -2, -2])  ->  [-2, -2, -2]

Constraints

• 2 <= len(asteroids) <= 10^4; -1000 <= asteroids[i] <= 1000, never 0.

Clarifying questions

• Do a left-mover followed by a right-mover ever collide? (No.)
• Do equal sizes both explode?
• Is order preserved for survivors?

What a strong answer covers

• A stack of survivors. For each left-mover, pop smaller right-movers off the top; stop at a larger one, cancel with an equal one, or push it if nothing is left to hit.
• O(n) time, since each asteroid is pushed and popped at most once.
• Tests: all one direction, a large left-mover clearing the stack, equal sizes.

Follow-ups

• Asteroids have different speeds.
• Return the order in which asteroids exploded.
• Two asteroids that meet merge into one of combined size.