Asteroid Collision

mediumStack65 stepsJava · Python · C++

Positive asteroids move right, negative ones left; when they meet, the smaller explodes (both if equal). Use a stack of survivors: a left-moving asteroid fights right-movers on top of the stack until it dies, they all die, or no right-mover is left.

▶ Watch the animated trace

Traced input: asteroids = [5, 10, -5, 3, -12, 4] → [-12, 4]. Original problem: neetcode.io/problems/asteroid-collision

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Each asteroid is pushed and popped at most once.

Key idea

Only a right-mover (top, positive) followed by a left-mover (current, negative) can collide.
While the top is smaller, it explodes: pop and keep fighting.
Equal sizes: pop the top and the current one dies too.
If the current asteroid survives, push it.

Common mistakes

Treating [-2, 2] as a collision; they move apart.
Forgetting the equal-size case.
Using an ArrayList and removing from the middle is O(n²).

Solution

Java

int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < asteroids.length; i++) {
        int a = asteroids[i];
        boolean alive = true;
        while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
            int top = stack.peek();
            if (top < -a) {
                stack.pop();
                continue;
            }
            if (top == -a) {
                stack.pop();
            }
            alive = false;
        }
        if (alive) {
            stack.push(a);
        }
    }
    int[] res = new int[stack.size()];
    for (int i = res.length - 1; i >= 0; i--) res[i] = stack.pop();
    return res;
}

Python

def asteroidCollision(asteroids: List[int]) -> List[int]:
    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()
                continue
            if top == -a:
                stack.pop()
            alive = False
        if alive:
            stack.append(a)
    return stack

C++

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

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Equal sizes Both explode.	`asteroids = [8, -8]`	`[]`
Moving apart Left-movers on the left and right-movers on the right never meet.	`asteroids = [-2, -1, 1, 2]`	`[-2, -1, 1, 2]`
One big left-mover -10 destroys all three.	`asteroids = [1, 2, 3, -10]`	`[-10]`
Left-mover dies -5 beats 2 but loses to 10.	`asteroids = [10, 2, -5]`	`[10]`