DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Asteroid Collision

mediumStack and queue

Problem statement

A row of asteroids is given as a list of non-zero integers. The absolute value is an asteroid's size and the sign is its direction: positive moves right, negative moves left. All asteroids move at the same speed.

When a right-moving asteroid meets a left-moving one, the smaller one explodes. If they are the same size, both explode. Asteroids moving in the same direction never meet, and a left-moving asteroid to the left of a right-moving one moves away from it.

Return the asteroids that are left once no more collisions can happen, in their original left-to-right order.

Examples

Example 1

Input: asteroids = [4, 9, -6]

Output: [4, 9]

Explanation: -6 hits 9 first. 9 is bigger, so -6 explodes and never reaches 4.

Example 2

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

Output: [-3, 2]

Explanation: 7 and -7 are the same size and both explode. -3 then has nothing to its left moving right, and 2 moves away from it.

Hints

Approach

The survivors to the left of any point form a stack: the only one a new asteroid can hit is the last survivor.

  1. For each asteroid, if it moves right, or the stack is empty, or the top moves left, just push it. No collision is possible.
  2. If it moves left and the top moves right, they collide:
    • top is smaller: pop it and check the next top with the same incoming asteroid;
    • equal size: pop it, and the incoming one is also gone;
    • top is bigger: the incoming one is gone.
  3. If the incoming asteroid survives all collisions, push it.

The stack, read bottom to top, is the answer. Every asteroid is pushed and popped at most once.

ComplexityTime O(n)Space O(n)
Python
class Solution:
def asteroidCollision(self, asteroids: list[int]) -> list[int]:
stack = [] # survivors so far, left to right
for rock in asteroids:
alive = True
while alive and rock < 0 and stack and stack[-1] > 0:
if stack[-1] < -rock: # top is smaller: it explodes, keep checking
stack.pop()
elif stack[-1] == -rock: # same size: both explode
stack.pop()
alive = False
else: # top is bigger: incoming one explodes
alive = False
if alive:
stack.append(rock)
return stack

Follow-up questions

  • Return how many collisions happened as well as the survivors.
  • What changes if asteroids can have different speeds?

Frequently asked questions

The -2 moves left and the 1 moves right, so they move apart. A collision needs a positive value on the left and a negative value on the right.

One large left-moving asteroid can destroy several smaller right-movers in a row, as in [3, 5, -8]. It has to keep going until it is stopped or the stack runs out of right-movers.

It is a clean example of resolving events against the most recent unresolved item, which is the same shape as matching open and close events in a log or cancelling a queued deploy with a later rollback.