Asteroid Collision
Medium Stack simulation
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Asteroids move along a line: positive values go right, negative go left, absolute value is size. When two collide, the smaller explodes; equal sizes both explode. Return the survivors.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: right-moving and left-moving asteroids crash; what's left?
Why this works: only a left-mover arriving after a right-mover collides. The stack holds survivors; the new left-mover fights the top.
Example: [5, 10, -5]
5, 10 on stack-5 meets 10 → -5 explodes → [5, 10]
✦Hints open one at a time
↗Approach
For each asteroid a: while a < 0 and the top is positive and smaller than |a|, pop. Then if the top is positive and equal to |a|, pop it and drop a; if the top is positive and bigger, drop a; otherwise push a.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Deque<Integer> st = new ArrayDeque<>();
for (int a : asteroids) {
boolean alive = true;
while (alive && a < 0 && !st.isEmpty() && st.peek() > 0) {
int top = st.peek();
if (top < -a) { st.pop(); continue; } // top explodes, keep fighting
if (top == -a) st.pop(); // both explode
alive = false; // a explodes
}
if (alive) st.push(a);
}
int[] res = new int[st.size()];
for (int i = res.length - 1; i >= 0; i--) res[i] = st.pop();
return res;
}
}!Common mistake
Making a left-mover collide with a left-mover or a right-mover that comes after it.
- Time: O(n).
- Space: O(n).