Start practising

Asteroid Collision

Medium Stack Stack Basics Original on LeetCode

Asteroid Collision is a medium stack problem solved with the stack basics pattern. The best approach, optimal (stack), runs in O(n) time and O(n) space. Below are 2 approaches in Java, from brute force (repeated simulation) up.

Problem

Each value in asteroids is an asteroid in a row: its absolute value is its size and its sign is its direction (positive moves right, negative moves left). All move at the same speed. When two meet, the smaller one explodes; if they are equal, both explode. Return the asteroids left after all collisions, in order.

Examples

Example 1

Input
asteroids = [6, 4, -5]
Output
[6]
Why
4 and -5 collide, -5 survives, then 6 destroys -5.

Example 2

Input
asteroids = [7, -7]
Output
[]
Why
Equal size: both explode.

Example 3

Input
asteroids = [-3, 2]
Output
[-3, 2]
Why
Moving apart, so they never meet.

Constraints

  • 2 <= asteroids.length <= 10^4
  • Values are non-zero; sign is direction (positive = right).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (repeated simulation)O(n²)O(n)
Optimal (stack)O(n)O(n)

1Brute force (repeated simulation)

TimeO(n²)
SpaceO(n)

Scan for any adjacent pair (positive, negative), resolve it, and rescan until nothing changes.

  1. Keep a list; find the first i with a[i] > 0 and a[i+1] < 0.
  2. Remove the smaller (or both if equal) and repeat.
Java
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        List<Integer> a = new ArrayList<>();
        for (int x : asteroids) a.add(x);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i + 1 < a.size(); i++) {
                int l = a.get(i), r = a.get(i + 1);
                if (l > 0 && r < 0) {
                    if (l > -r) a.remove(i + 1);
                    else if (l < -r) a.remove(i);
                    else { a.remove(i + 1); a.remove(i); }
                    changed = true;
                    break;
                }
            }
        }
        return a.stream().mapToInt(Integer::intValue).toArray();
    }
}

2Optimal (stack)

TimeO(n)Each asteroid is pushed and popped at most once.
SpaceO(n)

The stack holds survivors. A left-mover pops smaller right-movers from the top. If it meets an equal one, both die. If it meets a bigger one, it dies. If it clears all right-movers, it is pushed.

  1. Right-movers are pushed.
  2. For a left-mover x: while top > 0 and top < -x, pop.
  3. If top == -x, pop and drop x. Else if the stack is empty or top < 0, push x. Otherwise x is destroyed.
Java
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> st = new ArrayDeque<>();
        for (int x : asteroids) {
            if (x > 0) { st.push(x); continue; }
            while (!st.isEmpty() && st.peek() > 0 && st.peek() < -x) st.pop();
            if (!st.isEmpty() && st.peek() == -x) st.pop();
            else if (st.isEmpty() || st.peek() < 0) st.push(x);
        }
        int[] out = new int[st.size()];
        for (int i = out.length - 1; i >= 0; i--) out[i] = st.pop();
        return out;
    }
}

Edge cases to test

  • Equal sizes destroy each other
  • A left-mover destroys several right-movers in a row
  • Left-movers before any right-mover never collide

Hints

Hint 1

Only a right-mover followed by a left-mover can collide. The left-mover fights the most recent survivors first.

FAQ

What is the best time complexity for Asteroid Collision?

Optimal (stack) runs in O(n) time and O(n) extra space. Each asteroid is pushed and popped at most once.

Which pattern does Asteroid Collision use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Min Stack.

Is there a brute force solution for Asteroid Collision?

Yes. Brute force (repeated simulation) takes O(n²) time and O(n) space. Scan for any adjacent pair (positive, negative), resolve it, and rescan until nothing changes.

Which edge cases should I test for Asteroid Collision?

Equal sizes destroy each other; A left-mover destroys several right-movers in a row; Left-movers before any right-mover never collide.