LeetCode: Asteroid Collision

Determine the state of asteroids after all possible collisions.

Posted on 2 Dec 2025 LeetCode Python

Difficulty: Medium

Solution

First, determine if a collision will occur. This will only happen when a right-moving asteroid (positive value) meets a left-moving asteroid (negative value).

If the two colliding asteroids have equal magnitudes, both will be destroyed (pop() and break).
If the left-moving asteroid has a larger magnitude, the right-moving asteroid will be destroyed (pop()).
If the right-moving asteroid has a larger magnitude, the left-moving asteroid will be destroyed (break).

If there is no collision, simply append the asteroid to the stack.

Runtime

5 ms | Beats 70.62%

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []

        for x in asteroids:
            while True:
                # A collision is only possible if:
                # 1. stack is not empty
                # 2. stack[-1] > 0 and x < 0
                if stack and stack[-1] > 0 and x < 0:
                    # Collision
                    if stack[-1] + x == 0:
                        stack.pop(-1)
                        break
                    elif stack[-1] + x < 0:
                        stack.pop(-1)
                    else:
                        break
                else:
                    # No collision
                    stack.append(x)
                    break

        return stack