735. Asteroid Collision

Medium · solved 2026-10-02 · Open on LeetCode

stackarraysimulation

Time O(n) · Space O(n)

How to get there

Only right then left collides

1. Find which asteroids can meet. Two asteroids meet only when the one on the left moves right and the one on the right moves left. Every other combination moves apart or in the same direction, so it never collides.

2. Read left to right by hand and find where you get stuck. On [10, 2, -5]: 10 moves right, and nothing can hit it yet, but a later left-mover might. The same for 2. So every right-mover has to be kept, unresolved, until a left-mover arrives.

3. Notice which kept asteroid a left-mover hits first. The nearest one: the right-mover kept last. If it wins, it goes on to the one kept before that. Last kept, first hit: the survivors form a stack, and a left-mover works down from its top. On [10, 2, -5], -5 destroys 2, then meets 10 and explodes.

4. List how a left-mover’s run ends. It meets an equal right-mover and both explode; it meets a bigger right-mover and it explodes; or the stack is empty, or its top moves left too, and it survives for good.

5. Check the cost. The loop inside the loop looks quadratic, but each asteroid is pushed at most once and popped at most once, so the whole pass is O(n).

The reusable recipe: when a new element can remove several of the most recent survivors, keep the survivors on a stack and pop in a while loop until it stops.

Let the variables' meanings write the branches

Variable	Always means
`stack`	the asteroids read so far that are still alive, left to right
`asteroid`	the asteroid being placed; `0` once it has exploded

Code	What happened	What it restores
`while asteroid < 0 and stack and stack[-1] > 0:`	a collision is possible: the new one moves left, the top moves right	the loop runs exactly as long as one is
`if abs(asteroid) == stack[-1]:` then `asteroid = 0`, `stack.pop()`	equal sizes	both are gone
`elif abs(asteroid) > stack[-1]:` then `stack.pop()`	the new one is bigger	the top is gone; the new one meets the next top
`else: asteroid = 0`	the top is bigger	the new one is gone; the top stays
`if asteroid != 0: stack.append(asteroid)`	the run ended	a survivor joins the stack

Using 0 for “exploded” is safe because the constraints rule out an asteroid of size 0.

The method carries over: when one input can change several stack entries, the while condition is the situation in which a change is possible, and each branch inside is one outcome of it.

Alternatives compared

Approach	Time	Space	How it works
Repeated passes	O(n²)	O(n)	Scan for a right-mover followed by a left-mover, resolve that collision, and start again until a scan finds none.
Stack (chosen)	O(n)	O(n)	Keep the survivors on a stack; each left-mover pops the smaller right-movers on top until it explodes or survives.
Stack inside the input	O(n)	O(1) extra	The same stack, stored in the front of `asteroids` with a write index, so no second list is needed.

The stack resolves each collision the moment the left-mover arrives, so no asteroid is looked at again after it explodes. The repeated passes rescan the survivors after every collision.

solution.py

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

        for i, num in enumerate(asteroids):
            asteroid = num
            while asteroid < 0 and stack and stack[-1] > 0:
                if abs(asteroid) == stack[-1]:
                    asteroid = 0 # ignore
                    stack.pop()
                elif abs(asteroid) > stack[-1]:
                    stack.pop()
                else:
                    asteroid = 0 # ignore

            if asteroid != 0:
                stack.append(asteroid)

        return stack

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.