AlgoMaster Logo

Asteroid Collision

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

Asteroids sit in a row. Positive asteroids move right, negative asteroids move left, all at the same speed. When a right-moving asteroid meets a left-moving one, the bigger asteroid survives and the smaller one explodes. Equal sizes destroy each other.

Not every pair of asteroids can meet. Two positives travel in the same direction and never collide, and the same holds for two negatives. A negative followed by a positive moves apart. The only collision scenario is a positive asteroid with a negative asteroid somewhere to its right.

A collision can also trigger a chain reaction: when an asteroid is destroyed, the survivor may then collide with whatever came before it. The asteroid involved in the next collision is always the most recent survivor, and that "most recent first" order is what points to a stack.

Key Constraints:

  • 2 <= asteroids.length <= 10^4 → An O(n^2) simulation runs up to 10^8 operations, which is borderline. The target is O(n).
  • -1000 <= asteroids[i] <= 1000 → Sizes are small integers, so there are no overflow concerns. The sign encodes direction.
  • asteroids[i] != 0 → Every asteroid has a direction; there are no stationary asteroids.

Approach 1: Brute Force Simulation

Intuition

Simulate the collisions step by step. Scan the current state from left to right for a collision pair: a positive asteroid immediately followed by a negative one. Resolve it by removing whichever asteroid is destroyed (or both, on a tie), then restart the scan from the beginning, because the removal can bring a new positive-negative pair together.

The order in which pairs are resolved does not change the outcome. Each collision involves only the two asteroids in the pair, so resolving any valid pair first leaves the same final set of survivors. The scan repeats until it completes without finding a pair, and what remains is the answer.

Algorithm

  1. Copy the asteroids into a mutable list.
  2. Repeatedly scan the list from left to right:
    • Look for an index where list[i] > 0 and list[i+1] < 0 (a collision pair).
    • If found, resolve the collision:
      • If |list[i]| > |list[i+1]|, remove list[i+1] (the left-mover is destroyed).
      • If |list[i]| < |list[i+1]|, remove list[i] (the right-mover is destroyed).
      • If they are equal, remove both.
    • Set a flag indicating a collision was resolved, and restart the scan.
  3. When a full scan completes with no collisions, return the list.

Visualization and Code

Loading animation...

Restarting the scan after every collision is what makes this quadratic. The next approach resolves each collision the moment it becomes possible, so nothing is ever rescanned.

Approach 2: Stack

Intuition

Process asteroids from left to right and keep the survivors so far in a stack. A right-moving asteroid can never collide with anything already processed, so it is pushed immediately. A left-moving asteroid collides first with the most recent surviving right-mover, and if it wins, with the next most recent, and so on. That "most recent first" order is LIFO, which is what a stack provides.

So when a negative asteroid arrives, compare it against the top of the stack. Pop every smaller positive asteroid it destroys. Stop when the new asteroid is itself destroyed (the top is larger, or both are equal and destroy each other) or when no right-mover remains on top, in which case the new asteroid survives and is pushed.

Algorithm

  1. Initialize an empty stack.
  2. For each asteroid in the array:
    • Set a flag alive to true (the current asteroid has not been destroyed yet).
    • While alive is true, the stack is not empty, the current asteroid is negative, and the top of the stack is positive:
      • Compare sizes: if the top of the stack is smaller, pop it (it is destroyed). The current asteroid continues.
      • If the top of the stack is the same size, pop it and mark the current asteroid as destroyed too.
      • If the top of the stack is larger, mark the current asteroid as destroyed.
    • If alive is still true, push the current asteroid onto the stack.
  3. Return the stack contents as the result array.

Visualization and Code

Loading animation...

The stack costs O(n) extra memory. The final approach removes it by reusing the input array as the stack.

Approach 3: In-Place Stack

Intuition

The stack in Approach 2 only ever holds asteroids that have already been read from the input. The input array therefore has room for it: keep a write index j and treat asteroids[0..j) as the stack, with asteroids[j - 1] as the top. Pushing becomes writing at position j and incrementing it; popping becomes decrementing it.

This is safe because j never gets ahead of the read position. Each iteration reads one element into a local variable before writing, and j grows by at most one per element, so writes only overwrite positions that have already been read.

The collision logic is unchanged. Only the storage moves, which brings extra space down from O(n) to O(1). The returned prefix is the required output, not working memory.

Algorithm

  1. Initialize a write index j = 0. The prefix asteroids[0..j) acts as the stack.
  2. For each asteroid a in the array:
    • While a has not been destroyed, j > 0, a is negative, and asteroids[j - 1] is positive:
      • If asteroids[j - 1] < -a, decrement j (the top is destroyed) and keep checking.
      • If asteroids[j - 1] == -a, decrement j and mark a destroyed.
      • If asteroids[j - 1] > -a, mark a destroyed.
    • If a survived, write asteroids[j] = a and increment j.
  3. Return the first j elements.

Visualization and Code

Loading animation...