Asteroid Collision
Medium · Stack · Explanation and code example
Without Stack
How it works
We can simulate the stack behavior using the input array itself. We maintain a pointer j that tracks the "top" of our virtual stack within the array. When collisions occur, we decrement j (like popping). Surviving asteroids are written to position j + 1. This gives us O(1) extra space while maintaining the same logic.
Steps
- Use pointer
j = -1to represent an empty stack. - For each asteroid, handle collisions by comparing with
asteroids[j]when both are in opposite directions. - If the current asteroid survives, increment
jand store it atasteroids[j]. - If destroyed, skip storing it.
- Return the subarray from index
0toj(inclusive).
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)for the output array.
Things to watch for
Assuming All Asteroids Collide
Not all asteroids collide. Two asteroids moving in the same direction (both positive or both negative) never collide. A negative asteroid followed by a positive asteroid also never collide since they move apart.
Forgetting Chain Reactions
A single incoming asteroid can destroy multiple asteroids on the stack. You need a loop, not just a single comparison.
Incorrect Size Comparison
When comparing asteroid sizes, remember that negative asteroids have negative values. Use absolute value for size comparison.
Python code example
from typing import List
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
n = len(asteroids)
j = -1
for a in asteroids:
while j >= 0 and asteroids[j] > 0 and a < 0:
if asteroids[j] > abs(a):
a = 0
break
elif asteroids[j] == abs(a):
j -= 1
a = 0
break
else:
j -= 1
if a:
j += 1
asteroids[j] = a
return asteroids[:j + 1]
C++ code example
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
int n = asteroids.size();
int j = -1;
for (int& a : asteroids) {
while (j >= 0 && asteroids[j] > 0 && a < 0) {
if (asteroids[j] > abs(a)) {
a = 0;
break;
} else if (asteroids[j] == abs(a)) {
j--;
a = 0;
break;
} else {
j--;
}
}
if (a != 0) {
asteroids[++j] = a;
}
}
asteroids.resize(j + 1);
return asteroids;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.