Asteroid Collision
- 1 min read
- Stacks
- LC-Medium
3 years ago
Solution
- Use a stack because multiple collisions may happen one after the other- the stack keeps track of the asteroids going right
- If an asteroid is going left and the stack is empty or the stack top's asteroid is smaller, you just append the asteroid because it is not going to collide.
- Asteroids only collide when there's a stack top asteroid going right and the current asteroid is going left.
- Depending on the values of these asteroids, different things can happen
- Just look at the code and you will understand
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
while stack and stack[-1] > 0 and a < 0:
diff = a + stack[-1]
if diff < 0:
stack.pop()
elif diff > 0:
a = 0
else:
stack.pop()
a = 0
if a:
stack.append(a)
return stack