LeetCode 735: Asteroid Collision

Problem Restatement

We are given an integer array asteroids.

Each integer represents one asteroid.

The absolute value is the asteroid size.

The sign is its direction:

All asteroids move at the same speed.

When two asteroids collide:

We need to return the final state after all collisions. A collision only happens when a right-moving asteroid is before a left-moving asteroid. The official problem defines positive values as moving right, negative values as moving left, and asks for the state after all collisions.

Input and Output

Example function shape:

def asteroidCollision(asteroids: list[int]) -> list[int]:
    ...

Examples

Example 1

asteroids = [5, 10, -5]

The asteroid 10 moves right.

The asteroid -5 moves left.

They collide.

Since 10 is larger than 5, -5 explodes.

The result is:

[5, 10]

Example 2

asteroids = [8, -8]

The two asteroids collide.

They have the same size, so both explode.

The result is:

[]

Example 3

asteroids = [10, 2, -5]

First, 2 and -5 collide.

-5 has size 5, so it destroys 2.

Now 10 and -5 collide.

10 is larger, so -5 explodes.

The result is:

[10]

Example 4

asteroids = [-2, -1, 1, 2]

The negative asteroids move left.

The positive asteroids move right.

They are moving away from each other, so no collision happens.

The result is:

[-2, -1, 1, 2]

First Thought: Simulate Collisions

We can process asteroids from left to right.

When we see an asteroid, it may collide only with earlier asteroids that are still alive.

More specifically, a collision can happen only when:

previous asteroid > 0
current asteroid < 0

That means the previous asteroid is moving right and the current asteroid is moving left.

The closest previous asteroid matters first. If it explodes, the current asteroid may continue and collide with the next previous asteroid.

This last-survivor-first-collision behavior suggests a stack.

Key Insight

Use a stack to store asteroids that have survived so far.

For each new asteroid x:

• If x is moving right, push it.
• If x is moving left, it may collide with right-moving asteroids at the top of the stack.
• While the top of the stack is positive and x is negative, resolve the collision.

There are three collision outcomes:

If the current asteroid survives all possible collisions, push it onto the stack.

Algorithm

Create an empty stack.

For each asteroid x in asteroids:

1. Assume x is alive.
2. While x is alive, the stack is not empty, stack[-1] > 0, and x < 0:
   • If stack[-1] < -x, pop the stack.
   • Else if stack[-1] == -x, pop the stack and mark x as destroyed.
   • Else mark x as destroyed.
3. If x is still alive, append it to the stack.
4. Return the stack.

Correctness

The stack stores exactly the surviving asteroids among the prefix already processed, in their original order.

When the next asteroid moves right, it cannot collide with any previous asteroid immediately. Any previous right-moving asteroid moves in the same direction, and any previous left-moving asteroid is moving away from it. So pushing it is correct.

When the next asteroid moves left, it can collide only with previous right-moving asteroids. Among those, the nearest surviving one is at the top of the stack. Therefore resolving collision against stack[-1] first is correct.

If the top asteroid is smaller, it explodes, and the current asteroid may continue left into the next surviving asteroid. Popping and continuing is correct.

If both have equal size, both explode. Popping the top and discarding the current asteroid is correct.

If the top asteroid is larger, the current asteroid explodes. Keeping the stack unchanged is correct.

After all possible collisions for the current asteroid are resolved, if it remains alive, no previous surviving asteroid can collide with it. Therefore appending it preserves the stack invariant.

After every asteroid is processed, the stack contains exactly the final surviving asteroids.

Complexity

Let n = len(asteroids).

Even though there is a nested while loop, the total number of pops across the whole algorithm is at most n.

Implementation

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

        for x in asteroids:
            alive = True

            while alive and stack and stack[-1] > 0 and x < 0:
                top = stack[-1]

                if top < -x:
                    stack.pop()
                elif top == -x:
                    stack.pop()
                    alive = False
                else:
                    alive = False

            if alive:
                stack.append(x)

        return stack

Code Explanation

We use stack to store the asteroids that are still alive:

stack = []

For each asteroid, we track whether it survives:

alive = True

The collision loop runs only in the one possible collision direction:

while alive and stack and stack[-1] > 0 and x < 0:

If the stack top is smaller:

if top < -x:
    stack.pop()

the top asteroid explodes, and the current asteroid keeps moving left.

If both sizes are equal:

elif top == -x:
    stack.pop()
    alive = False

both explode.

If the stack top is larger:

else:
    alive = False

the current asteroid explodes.

After the loop, a surviving asteroid is stored:

if alive:
    stack.append(x)

Testing

def run_tests():
    s = Solution()

    assert s.asteroidCollision([5, 10, -5]) == [5, 10]
    assert s.asteroidCollision([8, -8]) == []
    assert s.asteroidCollision([10, 2, -5]) == [10]
    assert s.asteroidCollision([-2, -1, 1, 2]) == [-2, -1, 1, 2]

    assert s.asteroidCollision([1, -2]) == [-2]
    assert s.asteroidCollision([2, -1]) == [2]
    assert s.asteroidCollision([1, 2, 3, -6]) == [-6]
    assert s.asteroidCollision([-2, 2, -2, -1]) == [-2, -1]

    print("all tests passed")

run_tests()