Asteroid Collision — Solution in Python, Java & C++
Asteroid Collision solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Asteroid Collision is a medium coding problem on arrays, simulation and stack, asked in PhonePe, Sprinklr, Myntra and Dream11 interviews.
- Difficulty: Medium
- Topics: Arrays, Simulation, Stack
- Asked at: PhonePe, Sprinklr, Myntra, Dream11, Hotstar
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Asteroids move along a row: the absolute value is the size, the sign is the direction (positive → right, negative → left), all at equal speed.
When two asteroids meet, the smaller explodes (both explode if equal). Asteroids moving the same direction never meet. Return the state after all collisions.
Example 1
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: 10 destroys -5.
Example 2
Input: asteroids = [8,-8]
Output: []
Explanation: Equal sizes — both explode.
Example 3
Input: asteroids = [10,2,-5]
Output: [10]
Constraints
2 <= asteroids.length <= 30-100 <= asteroids[i] <= 100, asteroids[i] != 0
Hints for Asteroid Collision
Hint 1
Only a right-mover on the stack and an incoming left-mover collide.
Hint 2
Resolve collisions in a loop: the incoming asteroid may destroy several stack tops.
How to solve Asteroid Collision
There is exactly one collision pattern: something already moving right with something arriving that moves left. Every other pairing — two right-movers, two left-movers, or a left-mover already settled followed by a right-mover — drifts apart forever. So keep the settled asteroids on a stack and only fight when that one pattern appears.
Approach
- Process asteroids left to right, keeping the survivors on a stack.
- For the incoming asteroid
a, loop whileais moving left (a < 0) and the top of the stack is moving right (top > 0) — the only collision case. - If the top is smaller than
|a|, it explodes: pop it and keep looping, becauseamay plough into the next one too. - If they are the same size, both explode: pop the top and mark
adead. - If the top is bigger,
aexplodes and the top survives — stop. - If
asurvived the loop, push it.
Why it works
The stack always holds a settled configuration: no two asteroids in it can ever collide, because any right-mover sits above every left-mover that precedes it. A new asteroid can only disturb that from the right end, so resolving it against the top repeatedly is enough. Each asteroid is pushed once and popped at most once, so the cascading while still costs linear time overall.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The collision test needs both conditions. Checking only
a < 0makes left-movers wrongly attack other left-movers already on the stack. - Equal sizes destroy both asteroids — pop the top and stop the incoming one from being pushed.
- Keep looping after a win: one large left-mover can wipe out a whole run of right-movers.
- Compare magnitudes, not signed values: the incoming asteroid's size is
-awhenais negative.
Reference solution
Python
from typing import List
def asteroidCollision(asteroids: List[int]) -> List[int]:
st = []
for a in asteroids:
alive = True
while alive and a < 0 and st and st[-1] > 0:
top = st[-1]
if top < -a:
st.pop()
elif top == -a:
st.pop()
alive = False
else:
alive = False
if alive:
st.append(a)
return stJava
public static int[] asteroidCollision(int[] asteroids) {
int[] st = new int[asteroids.length];
int top = 0;
for (int a : asteroids) {
boolean alive = true;
while (alive && a < 0 && top > 0 && st[top - 1] > 0) {
int t = st[top - 1];
if (t < -a) {
top--;
} else if (t == -a) {
top--;
alive = false;
} else {
alive = false;
}
}
if (alive) st[top++] = a;
}
return Arrays.copyOf(st, top);
}C++
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> st;
for (int a : asteroids) {
bool alive = true;
while (alive && a < 0 && !st.empty() && st.back() > 0) {
int t = st.back();
if (t < -a) {
st.pop_back();
} else if (t == -a) {
st.pop_back();
alive = false;
} else {
alive = false;
}
}
if (alive) st.push_back(a);
}
return st;
}JavaScript
var asteroidCollision = function(asteroids) {
const st = [];
for (const a of asteroids) {
let alive = true;
while (alive && a < 0 && st.length > 0 && st[st.length - 1] > 0) {
const top = st[st.length - 1];
if (top < -a) {
st.pop();
} else if (top === -a) {
st.pop();
alive = false;
} else {
alive = false;
}
}
if (alive) st.push(a);
}
return st;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure