Asteroid Collision

medium array stack simulation

Problem

We are given an array asteroids of integers representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Inputasteroids = [5, 10, -5]

Output[5, 10]

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

asteroids (comma-separated, no zero)

def asteroid_collision(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 asteroidCollision(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[] asteroidCollision(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> asteroidCollision(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;
}

Explanation

Asteroids only collide in one situation: a right-moving one (positive) is followed by a left-moving one (negative). A stack is the natural tool, because the most recently surviving asteroid is exactly the one a newcomer might smash into first.

We process asteroids left to right. A new asteroid a is dangerous only when it moves left (a < 0) and the stack's top moves right (stack[-1] > 0). While that head-on setup holds, we resolve the collision by comparing sizes.

If the top is smaller than |a| (top < -a), the top is destroyed (pop it) and a keeps going, possibly hitting the next one. If they are equal in size, both blow up — pop the top and mark a as no longer alive. If the top is bigger, a is destroyed and the loop ends.

If a survives all collisions (or never had one), we push it onto the stack. Whatever remains on the stack at the end is the final lineup.

Example: asteroids = [5, 10, -5]. The -5 meets the top 10; since 10 > 5, the -5 is destroyed, leaving [5, 10].

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