Asteroid Collisions

medium array stack simulation

Problem

Each integer represents an asteroid: positive moves right, negative moves left, magnitude is its size. Asteroids moving toward each other collide; the smaller one explodes, equal sizes annihilate both. Return the survivors. Use a stack to track the still-moving column on the right.

Inputasteroids = [5, 10, -5]

Output[5, 10]

10 hits -5 head-on; 10 wins because |10| > |-5|.

asteroids (comma-separated, no zero)

def collide(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and a < 0 and stack and stack[-1] > 0:
            top = stack[-1]
            if top < -a: stack.pop()
            elif top == -a: stack.pop(); alive = False
            else: alive = False
        if alive: stack.append(a)
    return stack

function collide(asteroids) {
  const stack = [];
  for (const a of asteroids) {
    let alive = true;
    while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {
      const top = stack[stack.length - 1];
      if (top < -a) stack.pop();
      else if (top === -a) { stack.pop(); alive = false; }
      else alive = false;
    }
    if (alive) stack.push(a);
  }
  return stack;
}

class Solution {
    public int[] collide(int[] asteroids) {
        List<Integer> stack = new ArrayList<>();
        for (int a : asteroids) {
            boolean alive = true;
            while (alive && a < 0 && !stack.isEmpty() && stack.get(stack.size() - 1) > 0) {
                int top = stack.get(stack.size() - 1);
                if (top < -a) stack.remove(stack.size() - 1);
                else if (top == -a) { stack.remove(stack.size() - 1); alive = false; }
                else alive = false;
            }
            if (alive) stack.add(a);
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) res[i] = stack.get(i);
        return res;
    }
}

vector<int> collide(vector<int>& asteroids) {
    vector<int> stack;
    for (int a : asteroids) {
        bool alive = true;
        while (alive && a < 0 && !stack.empty() && stack.back() > 0) {
            int top = stack.back();
            if (top < -a) stack.pop_back();
            else if (top == -a) { stack.pop_back(); alive = false; }
            else alive = false;
        }
        if (alive) stack.push_back(a);
    }
    return stack;
}

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