Asteroid collision

Simulate asteroids moving right (positive) or left (negative) along a line, where a collision destroys the smaller one, using a stack of survivors.

The idea

Only a right-mover on the stack followed by a left-mover can collide, since two right-movers never meet and a left-mover followed by anything moving further left never meets either. Compare sizes: the smaller asteroid always explodes, and equal sizes destroy each other, so keep comparing the new asteroid against the stack until it either survives or is gone.

Code

public static int[] AsteroidCollision(int[] asteroids) {
    var stack = new Stack<int>();
    foreach (int a in asteroids) {
        int cur = a;
        while (cur != 0 && cur < 0 && stack.Count > 0 && stack.Peek() > 0) {
            int top = stack.Peek();
            if (Math.Abs(top) < Math.Abs(cur)) stack.Pop();
            else if (Math.Abs(top) == Math.Abs(cur)) { stack.Pop(); cur = 0; }
            else cur = 0;
        }
        if (cur != 0) stack.Push(cur);
    }
    return stack.Reverse().ToArray();
}

Tips

• Think of the stack as "everything still flying, left to right". A collision only ever happens against the top of it.
• Once an incoming asteroid explodes (cur becomes 0), stop: it cannot collide again.

In the .NET library

stack.Reverse() in C# walks a Stack<T> from top to bottom, so it has to be reversed again to read the survivors in their original left-to-right order.