Asteroid Collision

1. Define the problem

You are given a row of asteroids. Each number is one asteroid: its size is the absolute value , and its sign is the direction — positive moves right, negative moves left. All asteroids move at the same speed, so two of them only meet when a right-moving one is followed by a left-moving one. In that crash the smaller asteroid is destroyed, and if they are the same size both are destroyed. Two asteroids moving the same way never meet. Keep the survivors in a stack . A new left-moving asteroid has to fight the top of the stack over and over, because destroying one survivor exposes the next one behind it. Return the asteroids that are left, in their original left-to-right order.

Constraints

2 ≤ asteroids.length ≤ 10⁴
-1000 ≤ asteroids_i ≤ 1000
No asteroid has size 0
Two asteroids moving in the same direction never collide

Example

Inputasteroids = [10, 2, -5]

Output[10]

Explanation The -5 destroys the 2 because 5 is bigger than 2. It then meets the 10, which is bigger, so the -5 is destroyed and only the 10 survives.

2. Know the words first

In plain terms

Absolute value: The number with the minus sign removed. The absolute value of -5 is 5.
Stack: A pile where you add and remove only at the top. Here the top is the nearest surviving asteroid to the left.
Collision: What happens when a right-moving asteroid is directly followed by a left-moving one. They run into each other.

3. Visualize the solution

The row is the stack of surviving asteroids, left to right

0—

1—

2—

3—

Statusinit

Start with an empty stack of survivors.

What happens in this step

asteroids = [10, 2, -5]
stack = []

No asteroid has been processed yet, so every slot shows a dash.

Step 1 of 6

Steps to visualize

Each filled cell is an asteroid that is still alive. A dash means an empty slot.
A positive number moves right, a negative number moves left.
A right-moving asteroid is always pushed straight on, because nothing ahead of it can hit it yet.
A left-moving asteroid keeps fighting the top cell while that top cell is positive.
It pops smaller asteroids off, is destroyed by a bigger one, and both vanish when the sizes tie.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the stack of surviving asteroids, left to right

0—

1—

2—

3—

Statusinit

Start with an empty stack of survivors.

What happens in this step

asteroids = [10, 2, -5]
stack = []

No asteroid has been processed yet, so every slot shows a dash.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function asteroidCollision(asteroids) {
  const stack = [];

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

    while (alive && asteroid < 0 && stack.length > 0 && stack[stack.length - 1] > 0) {
      const top = stack[stack.length - 1];

      if (top < -asteroid) {
        stack.pop();
      } else {
        alive = false;

        if (top === -asteroid) {
          stack.pop();
        }
      }
    }

    if (alive) {
      stack.push(asteroid);
    }
  }

  return stack;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`asteroids = [10, 2, -5]`	`[10]`	example from the description, with two collisions in a row
`asteroids = [8, -8]`	`[]`	same size, so both asteroids are destroyed
`asteroids = [-2, -1, 1, 2]`	`[-2, -1, 1, 2]`	left movers before right movers, so nothing ever meets
`asteroids = [5, 10, -5]`	`[5, 10]`	the left mover is destroyed on its first collision
`asteroids = [1, 2, 3, -4]`	`[-4]`	one big left mover clears the whole stack
`asteroids = [-2, 1, 2, -3, 4]`	`[-2, -3, 4]`	a longer list mixing survivors on both sides

Asteroid Collision