Asteroid Collision

A row of asteroids is described by a non-zero integer array asteroids, listed from left to right. The absolute value of each entry is the asteroid's size; a positive sign means it flies to the right and a negative sign means it flies to the left. All asteroids move at the same speed.

When two asteroids meet, the smaller one is destroyed; if they are the same size, both are destroyed. Asteroids flying in the same direction never meet. Return the asteroids that survive once no more collisions can happen, in their left-to-right order.

Example 1

Example 2

Example 3

Constraints

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Pattern Path · Stacks · problem 47 of 169

Start simple

Repeatedly scan the row for an adjacent right-then-left pair, resolve one collision and rebuild the list until nothing changes: O(n²) time.

The key idea

Only a right-mover with a left-mover somewhere after it can collide. Scanning left to right, the survivors so far always look like this: some left-movers that have escaped (nothing to their left can catch them), followed by right-movers still drifting right. Keep them on a stack.

When the next asteroid moves right, it cannot hit anything that is already behind it, so push it. When it moves left, it meets the right-movers on the stack in reverse order, nearest first, which is exactly stack order:

• While the top is a right-mover smaller than it, that right-mover explodes: pop.
• If the top is a right-mover of the same size, both explode: pop and discard the new one.
• If the top is a bigger right-mover, the new asteroid explodes.
• If no right-mover is left on top, the new asteroid escapes: push it.

Every asteroid is pushed and popped at most once, so the whole simulation is linear, and the stack, read bottom to top, is the final left-to-right order.

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def asteroidCollision(self, asteroids):
        stack = []  # survivors so far, left to right
        for a in asteroids:
            alive = True
            # A left-mover hits the right-movers at the top of the stack.
            while alive and a < 0 and stack and stack[-1] > 0:
                top = stack[-1]
                if top < -a:
                    stack.pop()  # the right-mover explodes; keep going
                elif top == -a:
                    stack.pop()  # both explode
                    alive = False
                else:
                    alive = False  # the newcomer explodes
            if alive:
                stack.append(a)
        return stack

JavaScript

var asteroidCollision = function(asteroids) {
  const stack = []; // survivors so far, left to right
  for (const a of asteroids) {
    let alive = true;
    // A left-mover hits the right-movers at the top of the stack.
    while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {
      const top = stack[stack.length - 1];
      if (top < -a) {
        stack.pop(); // the right-mover explodes; keep going
      } else if (top === -a) {
        stack.pop(); // both explode
        alive = false;
      } else {
        alive = false; // the newcomer explodes
      }
    }
    if (alive) stack.push(a);
  }
  return stack;
};

What the interviewer is checking

The interviewer wants to see you spot the last-in-first-out structure of the collisions and handle the three outcomes (pop and continue, both destroyed, newcomer destroyed) without off-by-one bugs.

Mistakes to avoid

• Treating a left-mover followed by a right-mover (e.g. [-2, 3]) as a collision; they fly apart.
• Stopping after one collision, when a large left-mover can destroy several right-movers in a row.
• Forgetting the equal-size case, where both must disappear.
• Pushing the left-mover after it has already been destroyed.

Follow-ups to expect

• Return how many collisions happened. (Count pops and drops.)
• What if asteroids had different speeds? (Event-driven simulation with a priority queue.)
• Can you do it in place with O(1) extra space? (Use the input array as the stack.)

In real software

Matching opposing events in a stream, such as cancelling buy orders against sell orders or pairing opening and closing markers in parsers, uses the same stack-based cancellation.

Practice next