Asteroid Collision
Asteroid Collision is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (stack), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeated simulation) up.
Problem
Each value in asteroids is an asteroid in a row: its absolute value is its size and its 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 equal, both explode. Return the asteroids left after all collisions, in order.
Examples
Example 1
- Input
asteroids = [6, 4, -5]- Output
[6]- Why
- 4 and -5 collide, -5 survives, then 6 destroys -5.
Example 2
- Input
asteroids = [7, -7]- Output
[]- Why
- Equal size: both explode.
Example 3
- Input
asteroids = [-3, 2]- Output
[-3, 2]- Why
- Moving apart, so they never meet.
Constraints
2 <= asteroids.length <= 10^4- Values are non-zero; sign is direction (positive = right).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (repeated simulation) | O(n²) | O(n) |
| Optimal (stack) | O(n) | O(n) |
1Brute force (repeated simulation)
O(n²)O(n)Scan for any adjacent pair (positive, negative), resolve it, and rescan until nothing changes.
- Keep a list; find the first i with a[i] > 0 and a[i+1] < 0.
- Remove the smaller (or both if equal) and repeat.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
List<Integer> a = new ArrayList<>();
for (int x : asteroids) a.add(x);
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i + 1 < a.size(); i++) {
int l = a.get(i), r = a.get(i + 1);
if (l > 0 && r < 0) {
if (l > -r) a.remove(i + 1);
else if (l < -r) a.remove(i);
else { a.remove(i + 1); a.remove(i); }
changed = true;
break;
}
}
}
return a.stream().mapToInt(Integer::intValue).toArray();
}
}class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
a = list(asteroids)
changed = True
while changed:
changed = False
for i in range(len(a) - 1):
l, r = a[i], a[i + 1]
if l > 0 and r < 0:
if l > -r:
del a[i + 1]
elif l < -r:
del a[i]
else:
del a[i:i + 2]
changed = True
break
return aclass Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> a(asteroids.begin(), asteroids.end());
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i + 1 < (int)a.size(); i++) {
int l = a[i], r = a[i + 1];
if (l > 0 && r < 0) {
if (l > -r) a.erase(a.begin() + i + 1);
else if (l < -r) a.erase(a.begin() + i);
else a.erase(a.begin() + i, a.begin() + i + 2);
changed = true;
break;
}
}
}
return a;
}
};function asteroidCollision(asteroids) {
const a = [...asteroids];
let changed = true;
while (changed) {
changed = false;
for (let i = 0; i + 1 < a.length; i++) {
const l = a[i], r = a[i + 1];
if (l > 0 && r < 0) {
if (l > -r) a.splice(i + 1, 1);
else if (l < -r) a.splice(i, 1);
else a.splice(i, 2);
changed = true;
break;
}
}
}
return a;
}2Optimal (stack)
O(n)Each asteroid is pushed and popped at most once.O(n)The stack holds survivors. A left-mover pops smaller right-movers from the top. If it meets an equal one, both die. If it meets a bigger one, it dies. If it clears all right-movers, it is pushed.
- Right-movers are pushed.
- For a left-mover x: while top > 0 and top < -x, pop.
- If top == -x, pop and drop x. Else if the stack is empty or top < 0, push x. Otherwise x is destroyed.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Deque<Integer> st = new ArrayDeque<>();
for (int x : asteroids) {
if (x > 0) { st.push(x); continue; }
while (!st.isEmpty() && st.peek() > 0 && st.peek() < -x) st.pop();
if (!st.isEmpty() && st.peek() == -x) st.pop();
else if (st.isEmpty() || st.peek() < 0) st.push(x);
}
int[] out = new int[st.size()];
for (int i = out.length - 1; i >= 0; i--) out[i] = st.pop();
return out;
}
}class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
st = []
for x in asteroids:
if x > 0:
st.append(x)
continue
while st and st[-1] > 0 and st[-1] < -x:
st.pop()
if st and st[-1] == -x:
st.pop()
elif not st or st[-1] < 0:
st.append(x)
return stclass Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> st;
for (int x : asteroids) {
if (x > 0) { st.push_back(x); continue; }
while (!st.empty() && st.back() > 0 && st.back() < -x) st.pop_back();
if (!st.empty() && st.back() == -x) st.pop_back();
else if (st.empty() || st.back() < 0) st.push_back(x);
}
return st;
}
};function asteroidCollision(asteroids) {
const st = [];
for (const x of asteroids) {
if (x > 0) { st.push(x); continue; }
while (st.length > 0 && st[st.length - 1] > 0 && st[st.length - 1] < -x) st.pop();
if (st.length > 0 && st[st.length - 1] === -x) st.pop();
else if (st.length === 0 || st[st.length - 1] < 0) st.push(x);
}
return st;
}Edge cases to test
- Equal sizes destroy each other
- A left-mover destroys several right-movers in a row
- Left-movers before any right-mover never collide
Hints
Hint 1
Only a right-mover followed by a left-mover can collide. The left-mover fights the most recent survivors first.
FAQ
What is the best time complexity for Asteroid Collision?
Optimal (stack) runs in O(n) time and O(n) extra space. Each asteroid is pushed and popped at most once.
Which pattern does Asteroid Collision use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Min Stack.
Is there a brute force solution for Asteroid Collision?
Yes. Brute force (repeated simulation) takes O(n²) time and O(n) space. Scan for any adjacent pair (positive, negative), resolve it, and rescan until nothing changes.
Which edge cases should I test for Asteroid Collision?
Equal sizes destroy each other; A left-mover destroys several right-movers in a row; Left-movers before any right-mover never collide.