#735 - Asteroid Collision

MediumStack

Given an array asteroids of integers, the absolute value represents size and the sign represents direction (positive = moving right, negative = moving left). Asteroids moving the same direction never collide. When two asteroids meet, the smaller one explodes; if both are the same size, both explode. Find the state of the asteroids after all collisions.

Input	Output
asteroids = [5,10,-5]	[5,10]
asteroids = [8,-8]	[]
asteroids = [10,2,-5]	[10]

Solution Space

Try it

/**
 * Simulates asteroid collisions and returns the surviving asteroids.
 *
 * @param asteroids Array where |val| = size, sign = direction
 * @returns Array of asteroids remaining after all collisions
 */
export function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];

  for (const ast of asteroids) {
    let alive = true;

    // Collision only when stack top moves right (+) and current moves left (−)
    while (
      alive &&
      ast < 0 &&
      stack.length > 0 &&
      stack[stack.length - 1] > 0
    ) {
      const top = stack[stack.length - 1];

      if (top < -ast) {
        stack.pop(); // top asteroid is smaller — it explodes
      } else if (top === -ast) {
        stack.pop(); // equal size — both explode
        alive = false;
      } else {
        alive = false; // current asteroid is smaller — it explodes
      }
    }

    if (alive) stack.push(ast);
  }

  return stack;
}

Approach: stack – push each asteroid; when a left-moving asteroid meets a right-moving one on top, resolve collisions in a loop until the current asteroid is destroyed or no more collisions are possible.

Time: O(n) – each asteroid is pushed and popped at most once.

Space: O(n) – the stack can hold all asteroids in the worst case.

#394 Decode String

#2390 Removing Stars From a String