Problem Statement
You are given an array asteroids of integers: each represents an asteroid. The absolute value is its size; sign is direction: positive = moving right, negative = moving left. Asteroids moving in the same direction never meet. When two moving in opposite directions meet, the smaller one explodes; if they are the same size, both explode. Return the state of the asteroids after all collisions (order matters; left to right).
Key Observations
- Stack (simulate left-to-right): We process asteroids in order. Positive asteroids are pushed (they might be hit by a future negative from the right). For a negative asteroid: it moves left and can only collide with positive ones to its left (on the stack). Pop while stack has a positive top smaller than
|neg|(those explode); if top equals|neg|, pop and don't push the negative (both explode); if stack is empty or top is negative, push the negative (no collision with left).
Approach
High-level: Stack. For each a: if a>0 push. Else: while stack not empty and stack.peek()>0 and stack.peek() < -a pop; if stack not empty and stack.peek()==-a then pop and skip a; else if stack empty or stack.peek()<0 push a. Convert stack to array.
Steps: Deque<Integer> st; for (int a : asteroids) { if (a>0) st.push(a); else { while (!st.isEmpty() && st.peek()>0 && st.peek()<-a) st.pop(); if (!st.isEmpty() && st.peek()==-a) st.pop(); else if (st.isEmpty() || st.peek()<0) st.push(a); } } return st to array.
Implementation
public int[] asteroidCollision(int[] asteroids) {
Deque<Integer> st = new ArrayDeque<>();
for (int a : asteroids) {
if (a > 0) { st.push(a); continue; }
while (!st.isEmpty() && st.peek() > 0 && st.peek() < -a) {
st.pop();
}
if (st.isEmpty() || st.peek() < 0) {
st.push(a);
}
else if (st.peek() == -a) {
st.pop();
}
}
int[] out = new int[st.size()];
for (int i = out.length - 1; i >= 0; i--) {
out[i] = st.pop();
}
return out;
}Test Cases
Example 1
[5,10]Complexity Analysis
- Time: O(n).
- Space: O(n) for stack.
Follow-ups
- Previous smaller; range queries.