#735 Asteroid Collision

frequently reported atPayPal Oracle Amazon Uber Microsoft Bloomberg

the problem

In plain words

A row of asteroids is given as integers. The absolute value is an asteroid's size; 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 the same way never meet. Return what is left after every collision, in order.

in asteroids = [5,10,-5]

out [5,10]

−5 meets 10 and explodes. 5 and 10 move the same way, so they never meet.

in asteroids = [8,-8]

out []

Same size: both explode.

in asteroids = [10,2,-5]

out [10]

−5 destroys 2, then explodes against 10.

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack for matching & nesting Simulation

Only a right-mover followed by a left-mover can meet. Scan left to right and keep the survivors on a stack: a new left-mover fights the right-movers on top — the most recent one first — until it explodes or nothing is left to stop it.

solutions

From brute force to optimal

Find the first neighbouring pair → ←, remove the loser(s), and sweep again until no such pair is left.

Copy into an ArrayList.
Find the first i with list[i] > 0 and list[i + 1] < 0.
Remove the smaller (or both if equal) and restart the sweep.
Stop when a full sweep changes nothing.

timeO(n²)

Up to n collisions, and each one rescans the list and shifts it on removal.

spaceO(n)

The list copy.

javajava.util.*

1class Solution {2    public int[] asteroidCollision(int[] asteroids) {3        List<Integer> row = new ArrayList<>();4        for (int a : asteroids) row.add(a);5        boolean changed = true;6        while (changed) {                                  // keep sweeping until no pair can meet7            changed = false;8            for (int i = 0; i + 1 < row.size(); i++) {9                int left = row.get(i), right = row.get(i + 1);10                if (left > 0 && right < 0) {               // → ← : these two are heading for each other11                    if (left > -right) row.remove(i + 1);12                    else if (left < -right) row.remove(i);13                    else { row.remove(i + 1); row.remove(i); }14                    changed = true;15                    break;                                 // the row changed: start the sweep again16                }17            }18        }19        int[] result = new int[row.size()];20        for (int i = 0; i < result.length; i++) result[i] = row.get(i);21        return result;22    }23}

A right-mover is pushed and waits. A left-mover pops every smaller right-mover on top, then either dies (bigger or equal top) or is pushed.

For each a: alive = true.
While alive, a < 0 and the top is > 0: top < −a → pop (a flies on); top == −a → pop and a dies; top > −a → a dies.
If still alive, push a.
Copy the stack into an array, filling from the back (the top is the rightmost).

timeO(n)

Each asteroid is pushed once and popped at most once.

spaceO(n)

All asteroids survive when nobody collides.

javajava.util.*

1class Solution {2    public int[] asteroidCollision(int[] asteroids) {3        Deque<Integer> stack = new ArrayDeque<>();         // survivors so far; the top is the rightmost4        for (int a : asteroids) {5            boolean alive = true;6            while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) { // ← meets a → on top7                int top = stack.peek();8                if (top < -a) {9                    stack.pop();                           // the → is smaller: it explodes, a flies on10                } else {11                    if (top == -a) stack.pop();            // same size: both explode12                    alive = false;                         // a explodes either way13                }14            }15            if (alive) stack.push(a);16        }17        int[] result = new int[stack.size()];18        for (int i = result.length - 1; i >= 0; i--) result[i] = stack.pop(); // top = rightmost, so fill from the back19        return result;20    }21}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int[] asteroidCollision(int[] asteroids) {3        Deque<Integer> stack = new ArrayDeque<>();         // survivors so far; the top is the rightmost4        for (int a : asteroids) {5            boolean alive = true;6            while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) { // ← meets a → on top7                int top = stack.peek();8                if (top < -a) {9                    stack.pop();                           // the → is smaller: it explodes, a flies on10                } else {11                    if (top == -a) stack.pop();            // same size: both explode12                    alive = false;                         // a explodes either way13                }14            }15            if (alive) stack.push(a);16        }17        int[] result = new int[stack.size()];18        for (int i = result.length - 1; i >= 0; i--) result[i] = stack.pop(); // top = rightmost, so fill from the back19        return result;20    }21}

in the room

How to say it in the interview

talk track

Ask: same speed for all? Is 0 possible? (Same speed; never 0.)
Say which pairs can meet: only → followed by ←. A ← before a → are moving apart.
Say why a stack: the new left-mover hits the most recent unresolved right-mover first.
Defend O(n) with the push-once, pop-once argument.

traps

Letting ← then → collide — they move apart and never meet.
Forgetting the equal case: both must disappear, and the newcomer must not be pushed.
Building the answer by iterating the ArrayDeque: it goes top → bottom, so the result comes out reversed.

what they ask next

Follow-ups

Can you avoid boxing Integers?

Use an int[] as the stack with a top index, then return Arrays.copyOf(stack, top) — it's already in left-to-right order.

What if asteroids had different speeds?

Then collisions happen in time order, not just left-to-right order, so one stack is no longer enough. You'd work out meeting times and process the earliest collision first, for example with a priority queue.

before you submit

Edge cases to test

Equal sizes destroy each other: [8, −8] → [].
Left-movers at the start and right-movers at the end never collide: [−2, −1, 1, 2] stays the same.
One big left-mover can clear the row: [10, 2, 3, −20] → [−20].

practise next