Asteroid Collision With a Stack: O(n) Simulation

You're given an array asteroids of non-zero integers, all in a row. The absolute value is an asteroid's size and the sign is its direction (positive moves right, negative moves left), and they all move at the same speed. When two meet the smaller one explodes, and if they're the same size both do. Asteroids moving the same way never meet. Return the asteroids that are left once nothing more can collide, in their original order.

Examples

Input	Output	Why
`asteroids = [5, 10, -5]`	`[5, 10]`	The −5 hits the 10 and it's the −5 that explodes.
`asteroids = [8, -8]`	`[]`	They're the same size so both of them go.
`asteroids = [10, 2, -5]`	`[10]`	The −5 destroys the 2 and then the 10 destroys the −5.
`asteroids = [-2, -1, 1, 2]`	`[-2, -1, 1, 2]`	The two on the left are moving away from the two on the right, so nothing ever meets.

Constraints

1 ≤ n ≤ 10⁴
−1000 ≤ asteroids[i] ≤ 1000
asteroids[i] ≠ 0

Hints

Hint 1

It's only a right-mover with a left-mover somewhere after it that can collide, so which right-mover do you think a new left-mover hits first?

Hint 2

It's the nearest one before it that's still there, which is the last right-mover you've kept, and I'd say that sounds a lot like the top of a stack.

Hint 3

So you'd push right-movers, and for a left-mover you pop the smaller right-movers off the top until it either dies against a bigger one or takes an equal one with it (or survives, in which case it's pushed).

Where people lose marks

Letting a left-mover collide with a left-mover that's on the stack, when two asteroids going the same way never meet and the loop should only pop right-movers.
Forgetting about the equal case, where the left-mover and the top both explode and you mustn't push the left-mover afterwards.
Treating [−2, 2] as a collision. I'd draw it out, because the negative one's heading left and away from the other, and it's only a positive followed by a negative that can meet.

Dry run on `[10,2,-5,3,-3,-12]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 10

Step 1 / 10

asteroids
10021-5233-34-125
stack
I'd go left to right and keep a stack of the asteroids that haven't exploded yet.
Step 2 / 10

asteroids
10021-5233-34-125
stack
100
10 is moving right, and nothing behind it can ever catch it up, so it goes on the stack.
Step 3 / 10

asteroids
10021-5233-34-125
stack
10021
2 is another right-mover, so it goes on top and it's the first thing the next left-mover will hit.
Step 4 / 10

asteroids
10021-5233-34-125
stack
100
-5 hits the 2, and since 2 is the smaller of the two it explodes while -5 keeps on going.
Step 5 / 10

asteroids
10021-5233-34-125
stack
100
This time -5 runs into 10, which is bigger, so it's -5 that goes.
Step 6 / 10

asteroids
10021-5233-34-125
stack
10031
3 is another right-mover, so it goes on top and it's the first thing the next left-mover will hit.
Step 7 / 10

asteroids
10021-5233-34-125
stack
100
-3 and 3 are the same size so they take each other out.
Step 8 / 10

asteroids
10021-5233-34-125
stack
-12 hits the 10, and since 10 is the smaller of the two it explodes while -12 keeps on going.
Step 9 / 10

asteroids
10021-5233-34-125
stack
-120
Nothing's left in front of -12 that moves towards it, so it goes on the stack and won't hit anything again.
Step 10 / 10

stack
-120
What's left, from bottom to top, is [-12].

How to think about it

If you try to simulate the whole row step by step it's slow and fiddly. What I'd notice first is that only a right-mover with a left-mover somewhere after it can ever meet, and that a left-mover always hits the nearest right-mover in front of it that hasn't exploded yet.

So you go left to right with a stack of whatever's survived so far. A right-mover goes straight on the stack because nothing behind it can catch it up. For a left-mover you look at the top, and while that's a smaller right-mover it explodes and gets popped and the left-mover carries on. Then it ends one of three ways. If the top is a right-mover of the same size they both go, if it's a bigger right-mover it's the left-mover that goes, and if the stack's empty (or its top is moving left as well) there's nothing in the way and the left-mover gets pushed and won't ever hit anything again.

Each asteroid's pushed once and popped at most once so it's O(n), and you can read the answer off the stack from the bottom to the top.

Complexity. Time O(n) · Space O(n)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def asteroid_collision(asteroids):
    st = []
    for x in asteroids:
        alive = True
        while alive and x < 0 and st and st[-1] > 0:   # x moving left meets a right-mover
            if st[-1] < -x:
                st.pop()                # the right-mover explodes, x goes on
            elif st[-1] == -x:
                st.pop()                # both explode
                alive = False
            else:
                alive = False           # x explodes
        if alive:
            st.append(x)
    return st

#include <vector>

std::vector<int> solve(const std::vector<int>& asteroids) {
    std::vector<int> st;
    for (int x : asteroids) {
        bool alive = true;
        while (alive && x < 0 && !st.empty() && st.back() > 0) {   // x moving left meets a right-mover
            if (st.back() < -x) st.pop_back();                     // the right-mover explodes, x goes on
            else { if (st.back() == -x) st.pop_back(); alive = false; }   // both explode, or x does
        }
        if (alive) st.push_back(x);
    }
    return st;
}

import java.util.*;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> st = new ArrayDeque<>();
        for (int x : asteroids) {
            boolean alive = true;
            while (alive && x < 0 && !st.isEmpty() && st.peek() > 0) {   // x moving left meets a right-mover
                if (st.peek() < -x) st.pop();                            // the right-mover explodes, x goes on
                else { if (st.peek() == -x) st.pop(); alive = false; }   // both explode, or x does
            }
            if (alive) st.push(x);
        }
        int[] out = new int[st.size()];
        for (int i = out.length - 1; i >= 0; i--) out[i] = st.pop();
        return out;
    }
}

function asteroidCollision(asteroids) {
  const st = [];
  for (const x of asteroids) {
    let alive = true;
    while (alive && x < 0 && st.length && st[st.length - 1] > 0) {   // x moving left meets a right-mover
      const top = st[st.length - 1];
      if (top < -x) st.pop();                          // the right-mover explodes, x goes on
      else { if (top === -x) st.pop(); alive = false; } // both explode, or x does
    }
    if (alive) st.push(x);
  }
  return st;
}

fn solve(asteroids: &[i64]) -> Vec<i64> {
    let mut st: Vec<i64> = Vec::new();
    for &x in asteroids {
        let mut alive = true;
        while alive && x < 0 && !st.is_empty() && *st.last().unwrap() > 0 {   // x moving left meets a right-mover
            let top = *st.last().unwrap();
            if top < -x { st.pop(); }                                       // the right-mover explodes, x goes on
            else { if top == -x { st.pop(); } alive = false; }              // both explode, or x does
        }
        if alive { st.push(x); }
    }
    st
}

-- The stack is a list with its top at the head; reverse it at the end.
solve :: [Int] -> [Int]
solve = reverse . foldl push []
  where
    push st x | x > 0 = x : st
    push (t : rest) x
      | t > 0 && t < -x  = push rest x     -- the right-mover explodes, x goes on
      | t > 0 && t == -x = rest            -- both explode
      | t > 0            = t : rest        -- x explodes
    push st x = x : st                     -- nothing moving towards x

Variants to try

If the asteroids have different speeds it's no longer a stack problem: which pair meets first depends on the gaps, and you need an event queue ordered by meeting time.
If you're asked how many collisions happen, count the pops plus the times a left-mover dies, which you can do inside the same loop.

Next problems

Easy10 min

Asteroids that collide in a row

Examples

Constraints

Hints

Where people lose marks

Dry run on `[10,2,-5,3,-3,-12]`

How to think about it

The solution, in six languages

Variants to try

Next problems

Balanced brackets

Days until a warmer day

Evaluate reverse Polish notation

Keep going

Balanced brackets

Days until a warmer day

Evaluate reverse Polish notation

The pattern behind it

Asteroids that collide in a row

Examples

Constraints

Hints

Where people lose marks

Dry run on [10,2,-5,3,-3,-12]

How to think about it

The solution, in six languages

Variants to try

Next problems

Balanced brackets

Days until a warmer day

Evaluate reverse Polish notation

Keep going

Balanced brackets

Days until a warmer day

Evaluate reverse Polish notation

The pattern behind it

Dry run on `[10,2,-5,3,-3,-12]`