Course4all
Join us on telegram
Home/dsa/Stack/Asteroid Collision

Asteroid Collision

Master this topic with zero to advance depth.

Asteroid Collision

Calculate the final state of asteroids after all possible collisions. Positive integers move right, negative move left. If two asteroids meet, the smaller one explodes. If they are the same size, both explode.

Visual Representation

asteroids = [5, 10, -5] 1. 5: Push. Stack: [5] 2. 10: Push (same direction). Stack: [5, 10] 3. -5: Moves left. 10 > |-5|. -5 explodes. Final State: [5, 10]
Medium

Examples

Input: asteroids = [5,10,-5]
Output: [5,10]
Approach 1

Level I: Brute Force (Repeated Simulation)

Intuition

Repeatedly scan the list for the first pair of adjacent asteroids that collide (positive followed immediately by negative). Resolve it and restart from the beginning. Repeat until no more collisions exist.

⏱ O(N^2)💾 O(N)
java
import java.util.*;
public class Main {
    public static int[] asteroidCollision(int[] asteroids) {
        List<Integer> list = new ArrayList<>();
        for (int a : asteroids) list.add(a);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < list.size() - 1; i++) {
                int a = list.get(i), b = list.get(i + 1);
                if (a > 0 && b < 0) {
                    if (Math.abs(a) > Math.abs(b)) list.remove(i + 1);
                    else if (Math.abs(a) < Math.abs(b)) list.remove(i);
                    else { list.remove(i); list.remove(i); }
                    changed = true; break;
                }
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    public static void main(String[] args) { System.out.println(Arrays.toString(asteroidCollision(new int[]{5, 10, -5}))); }
}
Approach 2

Level III: Optimal (Stack Simulation)

Intuition

Use a stack to track asteroids moving right. When a left-moving asteroid appears, it collides with right-moving ones on the stack top. Continue popping from the stack as long as the right-moving asteroid is smaller. Handle tie-breaks where both explode.

⏱ O(N)💾 O(N)

Detailed Dry Run

AstActionStack StatusCollision Result
5Push[5]-
10Push[5, 10]-
-5Compare[5, 10]-5 explodes (10 > 5)
-12Compare[]10 explodes, 5 explodes, -12 stays
java
import java.util.*;

public class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            boolean exploded = false;
            while (!stack.isEmpty() && a < 0 && stack.peek() > 0) {
                if (stack.peek() < -a) {
                    stack.pop();
                    continue;
                } else if (stack.peek() == -a) {
                    stack.pop();
                }
                exploded = true;
                break;
            }
            if (!exploded) stack.push(a);
        }
        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; i--) res[i] = stack.pop();
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.asteroidCollision(new int[]{5,10,-5}))); // [5, 10]
    }
}

⚠️ Common Pitfalls & Tips

Be careful handle the case where a left-moving asteroid destroys everything in the stack and still survives. Also, ensure tie-cases (same size) are handled correctly.

← Previous QuestionGenerate Parentheses
Next Question →Remove All Adjacent Duplicates in String II