Colliding Asteroids

Tags

Colliding Asteroids

Category

Stacks

Difficulty

Medium

Problem Statement

Given an array of integers representing asteroids in a row, simulate their collisions. Each asteroid moves at the same speed. Positive values move right, negative values move left. When two asteroids meet, the smaller one explodes. If they are the same size, both explode. Asteroids moving in the same direction never collide. Return the state of the asteroids after all collisions.

Intuition

Collisions only happen when a right-moving asteroid (positive) is followed by a left-moving asteroid (negative). A stack naturally models this: we process asteroids left to right, and when a left-moving asteroid encounters right-moving asteroids on the stack, collisions occur. The stack acts as the current state of surviving right-moving asteroids.

Approach

  1. Initialize an empty stack.
  2. For each asteroid in the array: a. If the asteroid is moving right (positive), push it onto the stack. b. If the asteroid is moving left (negative):
    • While the stack is not empty and the top of the stack is positive and smaller than the absolute value of the current asteroid:
      • Pop the stack (the smaller right-moving asteroid is destroyed).
    • If the stack is not empty and the top equals the absolute value of the current asteroid:
      • Pop the stack (both are destroyed). Do not push the current asteroid.
    • Else if the stack is empty or the top is negative:
      • Push the current asteroid (it survives).
  3. Return the stack contents as the result.

Pseudocode

function collidingAsteroids(asteroids):
    stack = []
    for asteroid in asteroids:
        if asteroid > 0:
            stack.push(asteroid)
        else:
            while stack is not empty and stack.top() > 0 and stack.top() < abs(asteroid):
                stack.pop()
            if stack is not empty and stack.top() == abs(asteroid):
                stack.pop()  // both destroyed
            elif stack is empty or stack.top() < 0:
                stack.push(asteroid)
    return stack

Time & Space Complexity

  • Time: O(n) where n is the number of asteroids. Each asteroid is pushed and popped from the stack at most once.
  • Space: O(n) for the stack in the worst case (no collisions).

Key Insights

  • Only a positive asteroid followed by a negative asteroid causes a collision. Two negatives or two positives never collide.
  • The stack elegantly models the "pending" right-moving asteroids waiting for potential collisions.
  • A single large left-moving asteroid can destroy multiple smaller right-moving ones in sequence.
  • The while loop handles cascading collisions where one left-moving asteroid destroys several right-moving ones.

Edge Cases

  • All asteroids move in the same direction: no collisions, return the original array.
  • All asteroids are the same size but alternating directions: all pairs cancel out.
  • Single asteroid: return it as-is.
  • A very large left-moving asteroid at the end that destroys everything before it.
  • Adjacent asteroids of the same size but opposite directions: both are destroyed.
  • Left-moving asteroids appearing before any right-moving ones: they survive (nothing to collide with).

Linked mentions