A one-lane job fabric runs signed packets: positive ids travel right, negative left, abs is payload size. Opposite packets that meet destroy the smaller; equal size both vanish. Same-direction packets never meet. The intern version rescanned the lane after every blast. A dozen packets returned in milliseconds. A few thousand on the production fabric were still comparing neighbors when the dispatcher timed out.
Asteroid Collision asks which rocks survive after every head-on meet. A nested rescan uses that and still pays O(n²). Same-direction rocks never collide; only a right-goer with a left-goer to its right can meet.
This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about a deque of survivors so a left-goer pops every smaller right-goer still on top, not a restart of the lane. Same family as Daily Temperatures — that stack holds waiting indexes; this one holds survivor values. Do not re-solve the waits on this prompt.
The problem
Given an int[] asteroids, sign is direction (positive right, negative left) and absolute value is size. Same-direction asteroids never collide; opposite collide only when a right-goer sits left of a left-goer — the smaller explodes, equal size both explode. Return the survivors in order.
asteroids = [5, 10, -5] → [5, 10]
asteroids = [8, -8] → []
asteroids = [10, 2, -5] → [10]
asteroids = [-2, -1, 1, 2] → [-2, -1, 1, 2]First row: 10 and -5 meet; -5 is smaller and explodes; 5 never meets 10 (same direction). Second: equal size, both gone. Third: -5 explodes 2, then dies against 10. Fourth: they move apart, so the lane is unchanged.
Note: [-2, -1, 1, 2] stays as-is. Negative then positive means they move apart. Do not invent a wrap-around collision.
Nested rescan is the honest brute force
When a positive sits immediately left of a negative, explode the smaller (or both if equal), compact, and rescan from the left. Correct. Quadratic.
int[] asteroidCollisionRescan(int[] asteroids) {
List<Integer> live = new ArrayList<>();
for (int a : asteroids) {
live.add(a);
}
boolean exploded = true;
while (exploded) {
exploded = false;
List<Integer> next = new ArrayList<>();
int i = 0;
while (i < live.size()) {
if (i + 1 < live.size()
&& live.get(i) > 0
&& live.get(i + 1) < 0) {
int left = live.get(i);
int right = live.get(i + 1);
if (left > -right) {
next.add(left);
} else if (left < -right) {
next.add(right);
}
exploded = true;
i += 2;
} else {
next.add(live.get(i));
i++;
}
}
live = next;
}
int[] ans = new int[live.size()];
for (int i = 0; i < live.size(); i++) {
ans[i] = live.get(i);
}
return ans;
}At n = 20 this is a rounding error. At a few thousand you paid a rescan for a question a stack answers because each survivor is a candidate for many later left-goers at once: is the top a smaller right-goer I can explode?
Deque of survivors
The deque holds asteroids that have survived everything to their left. Walk left to right. Current is ast.
- A negative asteroid may collide with positive ones on top: while the deque is not empty,
peek() > 0, and-ast > peek(), pop — that right-goer is smaller. - If the top equals
-ast, pop and skip the push: both explode. - Push the left-goer only when it survived: the deque is empty or the top is negative. A larger positive still on top means this left-goer exploded — skip the push.
A positive ast never meets anyone already on the deque: a positive top is the same direction; a negative top is already to the left and they move apart. Push it.
Walk the samples. The deque stores values, not indexes.
asteroids = [5, 10, -5]
ast=5 [] push [5]
ast=10 top 5 same dir push [5, 10]
ast=-5 top 10 > 5 -5 dies [5, 10]
→ [5, 10]
asteroids = [8, -8]
ast=8 [] push [8]
ast=-8 top 8 == 8 pop, no push []
→ []
asteroids = [10, 2, -5]
ast=10 [] push [10]
ast=2 top 10 same dir push [10, 2]
ast=-5 top 2 < 5 pop [10]
top 10 > 5 -5 dies [10]
→ [10]
asteroids = [-2, -1, 1, 2]
ast=-2 [] push [-2]
ast=-1 top -2 same dir push [-2, -1]
ast=1 top negative push (apart) [-2, -1, 1]
ast=2 same dir right push [-2, -1, 1, 2]
→ [-2, -1, 1, 2]The -5 in the third sample popped 2 and then died against 10. That is the whole saving: one left-goer closes every smaller right-goer still on top, and you never rescan them.
The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack. Dump from the top into the array from the right so order is left-to-right again.
int[] asteroidCollision(int[] asteroids) {
Deque<Integer> live = new ArrayDeque<>();
for (int ast : asteroids) {
if (ast > 0) {
live.push(ast);
continue;
}
while (!live.isEmpty() && live.peek() > 0 && live.peek() < -ast) {
live.pop();
}
if (!live.isEmpty() && live.peek() == -ast) {
live.pop();
continue;
}
if (live.isEmpty() || live.peek() < 0) {
live.push(ast);
}
}
int n = live.size();
int[] ans = new int[n];
for (int i = n - 1; i >= 0; i--) {
ans[i] = live.pop();
}
return ans;
}Time is O(n) — each asteroid is considered once, and a survivor is pushed once and popped at most once. Space is O(n) for the deque (an all-right or all-left lane never pops). Do not quote the rescan O(n²) as the intended bill.
Equal size both explode — pop the top and skip the push; leaving either rock is a bug. [-2, -1, 1, 2] never collides — they move apart, so every value pushes.
What interviewers usually poke next
- Same monotonic family. Daily Temperatures holds waiting indexes; the wait is later minus earlier. This deque holds survivor values. Different payload. Do not re-solve the waits on this prompt.
- Count destroyed, not the leftover array. Same walk; increment on each pop and on a current that dies. Different return type. Do not rewrite this method into that one.
- Circular belt. A wrap-around meet is a second pass over the same idea, not a new ADT. Do not invent a second deque.
- All same sign. The
whilenever fires. The answer is a copy. Name it; the same loop handles it. - Zeros. The usual prompt is non-zero. A
0has no direction; at the board, ask.
You are done with this problem when you can walk [10, 2, -5] out loud, pop 2 then refuse the push of -5 against 10, and say why [-2, -1, 1, 2] never collides.