Asteroid Collision

Medium Problem 38 of 151 Java and Python

Problem

You are given an array asteroids in a row. The absolute value is each asteroid's size and the 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 the same size, both explode. Asteroids moving in the same direction never meet. Return the state after all collisions.

Example 1

Input: asteroids = [5, 10, -5]
Output: [5, 10]
Why: -5 hits 10 and explodes.

Example 2

Input: asteroids = [8, -8]
Output: []
Why: Equal sizes: both explode.

Example 3

Input: asteroids = [10, 2, -5]
Output: [10]
Why: -5 destroys 2, then 10 destroys -5.

Constraints

2 ≤ asteroids.length ≤ 10⁴
-1000 ≤ asteroids[i] ≤ 1000, asteroids[i] ≠ 0

Explanation

A collision only happens when a left-moving asteroid meets a right-moving one before it. The right-mover it hits first is the most recent survivor, which is the top of a stack.

So process left to right with a stack of survivors. A negative asteroid keeps destroying smaller positive tops until it is destroyed, ties, or finds no positive top.

Approach 1 · Naive

Repeat until no collisions

Time O(n²)
Space O(n)

Scan for an adjacent pair (positive, negative), resolve it, and start over until no such pair exists.

Find the first i with a[i] > 0 and a[i + 1] < 0.
Remove the smaller one (or both if equal).
Repeat until no pair is found.

Java

import java.util.*;

class Solution {
    public 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 + 1 < list.size(); i++) {
                int a = list.get(i);
                int b = list.get(i + 1);
                if (a > 0 && b < 0) {
                    if (a > -b) {
                        list.remove(i + 1);
                    } else if (a < -b) {
                        list.remove(i);
                    } else {
                        list.remove(i + 1);
                        list.remove(i);
                    }
                    changed = true;
                    break;
                }
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

Python

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        rocks = list(asteroids)
        changed = True
        while changed:
            changed = False
            for i in range(len(rocks) - 1):
                a, b = rocks[i], rocks[i + 1]
                if a > 0 and b < 0:
                    if a > -b:
                        del rocks[i + 1]
                    elif a < -b:
                        del rocks[i]
                    else:
                        del rocks[i:i + 2]
                    changed = True
                    break
        return rocks

Approach 2 · Optimal

Stack of survivors

Time O(n)
Space O(n)

Push asteroids that survive. A negative asteroid fights the positive tops of the stack until one side wins.

For each asteroid a: set alive = true.
While alive, a < 0 and the top is positive: if the top is smaller than -a, pop and continue; if equal, pop and set alive = false; if larger, set alive = false.
If still alive, push a.

Java

import java.util.*;

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

Python

class Solution:
    def asteroidCollision(self, 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()
                else:
                    alive = False
                    if top == -a:
                        stack.pop()
            if alive:
                stack.append(a)
        return stack

Complexity compared

Approach	Time	Space
Naive Repeat until no collisions	O(n²)	O(n)
Optimal Stack of survivors	O(n)	O(n)

Key takeaways

A negative on the left and a positive on the right move apart: no collision. Only (positive, then negative) collide.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem