Asteroid Collision | Stack Simulation | Stack

Overview

Asteroid collision: each asteroid has size (absolute value) and direction: positive = right, negative = left. When two move toward each other (positive on left, negative on right), the smaller explodes; if equal, both explode. Return the surviving asteroids in order. Stack: keep "survivors so far"; positive asteroids push; negative asteroids collide with top positives until they are destroyed or destroy the negative.

When to Use

Opposite-direction collision with "smaller loses" — stack of one direction, resolve the other.
Merging / cancellation where order matters — stack preserves left-to-right resolution.

How It Works

Stack = asteroids moving right that haven't been hit (or negatives that survived). For a positive a: push (nothing to the left can hit it now). For negative a: pop while top is positive and top < |a| (top explodes); if top === |a|, pop and skip a (both explode); if top > |a| or stack empty with only negatives, skip a; else push a only when stack is empty or top is negative.

Example 1: Standard Stack

function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];
  for (const a of asteroids) {
    if (a > 0) { stack.push(a); continue; }
    while (stack.length > 0 && stack[stack.length - 1] > 0 && stack[stack.length - 1] < -a) stack.pop();
    if (stack.length > 0 && stack[stack.length - 1] === -a) { stack.pop(); continue; }
    if (stack.length === 0 || stack[stack.length - 1] < 0) stack.push(a);
  }
  return stack;
}

Time: O(n). Space: O(n).

Example 2: Step-by-Step Trace

[5, 10, -5]. 5: push [5]. 10: push [5,10]. -5: top 10 > 5, pop 10? No, 10 > 5; -5 is destroyed. Stack [5]. Result [5].

[8, -8]. 8: [8]. -8: top 8 === 8, pop and skip → []. Result [].

[10, 2, -5]. 10, 2: [10, 2]. -5: pop 2 (2 < 5); top 10 > 5, -5 destroyed. Result [10].

Example 3: Edge Cases

All positive — push all; return as-is.
All negative — push all (they move left, never meet); return as-is.
Negative first — e.g. [-1, 1]: -1 pushed, 1 pushed; no collision (negative already left). Result [-1, 1].
Empty — return [].

Example 4: Same Logic, Explicit "alive" Flag

Instead of "skip current", use a boolean: after the while loop, if we didn't pop an equal or get stopped by a larger, push a. (Current code does this with the final if: push only when stack empty or top negative.)

Example 5: Return Count or Indices

If the problem asked for the number of survivors: return stack.length. If it asked for indices of surviving asteroids, track indices along with values in the stack (e.g. stack of { value, index }) and map result to indices.

Summary

Asteroid collision: stack for right-moving; for negative, pop smaller positives, handle equal (both gone), skip if destroyed by larger; push negative only when it survives. See Stack Basics.