One tiny chain reaction, a tempting wrong solution, and the O(n) reasoning worth taking into your next interview.
Before you scroll to the Python, try this tiny input in your head.
[4, 7, 3, -9]
Positive numbers move right, negative numbers move left, and the smaller asteroid disappears when two collide. So the 3 loses to -9, which feels like a perfectly reasonable place to finish one iteration.
Except -9 is still moving. It reaches 7 next, then 4, and suddenly the entire answer is [-9].
That is the little trap I like about LeetCode 735, Asteroid Collision. You can understand every rule and still write code that stops one collision too early. Honestly, this is exactly the kind of small problem I want in a practice session, because the mistake is specific enough to fix and the reasoning travels well.
Let’s work through it slowly enough to see the idea, then turn it into a solution you can explain without pointing vaguely at a stack.
First, make sure these two asteroids can actually meet
This is a Medium problem about a row of asteroids. Input order gives their relative positions, the absolute value gives their size, and the sign gives their direction. Every asteroid moves at the same speed.
When two meet, the smaller one disappears. If their sizes match, both disappear. We return the survivors in their original relative order.
Notice how much work that same-speed rule saves us. Two asteroids moving right cannot catch each other, and neither can two moving left. We do not need coordinates, elapsed time or a physics simulation.
Now compare [5, -3] with [-5, 3]. In the first pair, the asteroids move toward each other. In the second, they move apart, so comparing their sizes would already be a mistake.
While scanning from left to right, a collision is possible only when the latest surviving asteroid is positive and the incoming asteroid is negative. Check that relationship before comparing magnitudes.
I prefer drawing those two arrows once before touching the keyboard. It is much easier to catch a direction mistake on paper than inside three nested branches.
Keep the survivors, and look at the nearest one first
Imagine we have processed 4, 7 and 3. They all move right, so our survivors are [4, 7, 3]. When -9 arrives from the right, 3 is the first asteroid in its way.
If 3 disappears, 7 becomes the next one in its way. Removing 7 exposes 4. That access pattern gives us a stack, with the rightmost survivor at the top.
More precisely, after each input asteroid is fully processed, the stack contains the survivors of the prefix we have seen, in their original order, with no unresolved collisions among them.
That last sentence is the promise our code needs to keep. These are survivors so far; future input can still destroy them.
Also, this is not a stack sorted by size. [4, 7, 3] is completely valid, even though its magnitudes rise and fall. Calling every solution with a stack a monotonic-stack solution hides the actual reason we chose it. Here, we need the most recent surviving neighbor.
Stay with -9 until its story is finished
Our incoming asteroid gets its own little piece of state. It stays alive until a larger asteroid destroys it or an equal one destroys both. Popping a smaller neighbor does not finish the incoming asteroid’s turn.
Follow the same -9 through the entire sequence.
Compare 3 with size 9 and remove 3. Keep -9 available for another comparison.
Compare 7 with size 9 and remove 7. The stack now contains only 4.
Compare 4 with size 9 and remove 4. Nothing remains to block -9.
Append -9 once, after the collision loop finishes. The result is [-9].
This explains why a single if statement is not enough. It can resolve the collision with 3 and leave an unresolved collision between 7 and -9. A while loop keeps checking the boundary that each removal exposes.
There are only three outcomes to remember
Once the direction check passes, compare the positive stack top with the magnitude of the incoming negative asteroid.
If the top is smaller, pop it and keep the incoming asteroid alive. Another collision may be waiting underneath.
If the sizes match, pop the top and mark the incoming asteroid dead. Neither belongs in the result.
If the top is larger, leave it alone and mark the incoming asteroid dead. This arrival cannot reach anything farther left.
If the loop finishes with the incoming asteroid still alive, append it. That can happen because the stack is empty, because its top moves left too, or because the incoming asteroid moves right and cannot hit an earlier survivor.
Now the Python has a reason for every branch
I’m keeping the alive flag explicit here because it makes the difference between removing a neighbor and destroying the current asteroid easy to see. Shorter code can wait until the reasoning feels boring in the best possible way.
from typing import List
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
survivors = []
for asteroid in asteroids:
alive = True
while (
alive
and asteroid < 0
and survivors
and survivors[-1] > 0
):
if survivors[-1] < -asteroid:
survivors.pop()
elif survivors[-1] == -asteroid:
survivors.pop()
alive = False
else:
alive = False
if alive:
survivors.append(asteroid)
return survivors
Inside the loop, asteroid is negative, so -asteroid is its positive magnitude. We are comparing sizes, not deciding that a negative number must be smaller than a positive one.
Python evaluates the and conditions from left to right. The survivors check therefore protects survivors[-1] when the stack is empty.
Equality deserves its own branch. If you only pop the top and forget alive = False, the incoming asteroid gets appended afterward and quietly comes back from the dead. Cute in a movie, deeply unhelpful in an algorithm.
Why this keeps the stack’s promise
Before a new arrival, earlier survivors already have no unresolved collisions with each other. The only new conflict can be between the arrival and the rightmost survivor.
Removing that survivor exposes exactly one new neighbor, so the loop checks again. When the arrival dies, the earlier survivors are still stable. When it survives, the loop has established that it cannot collide with the remaining top, so appending it restores the same promise.
Repeat that for every input asteroid and the final stack contains exactly the survivors we need. We never reorder the input, which matters because position determines who meets whom.
Two loops do not automatically mean O(n²)
This is the explanation I want ready for the follow-up. One incoming asteroid can do a lot of work, but it does that work by permanently removing earlier asteroids.
Across the whole input, each asteroid is appended at most once and popped at most once. Once 3 has disappeared, a later arrival cannot make us pop that same 3 again.
A collision that does not pop anything destroys the incoming asteroid and ends its loop. There is at most one such final comparison per arrival. Equality also ends the loop while removing the top.
So the total work is O(n), including all those repeated collisions. The stack can hold all n asteroids when none collide, giving O(n) extra space. Python list append is amortized constant time, and removing its last element is constant time.
By comparison, repeatedly deleting from the middle of an array can shift many elements on every deletion. A stack lets us do the same local cleanup at the end of the list.
Four tiny cases make the explanation much harder to fake
Before calling the solution finished, hand-trace inputs that force different decisions. Each one should have a reason for existing.
[8, -8] becomes []. This checks that equality destroys both asteroids.
[-2, -1, 1, 2] stays unchanged. These asteroids either share a direction or move apart.
[10, 2, -5] becomes [10]. The incoming -5 removes 2, then loses to 10.
[4, 7, 3, -9] becomes [-9]. One arrival has to clear several smaller neighbors before it can be appended.
Then make the chain end in equality with [4, 7, 3, -7]. Remove 3, let 7 and -7 destroy each other, and leave [4]. This catches the version that handles equality correctly in isolation but continues after the incoming asteroid is already gone.
Take the reasoning into your next practice session
Close the implementation and reconstruct it from the stack’s promise. Explain which pair can collide, what each branch removes, and why the same incoming value sometimes needs another turn through the loop.
When that feels comfortable, pick another coding problem and write down what your data structure must keep true before you code. Let the problem determine the structure instead of hunting for a familiar template.
For this one, you should be able to explain why the last survivor matters, why one removal can expose another conflict, and why repeated work can still add up to linear time. Those are useful things to carry beyond an asteroid problem.
My favorite takeaway is that tiny examples can ask surprisingly honest questions. With just four numbers, this one tells you whether your code resolves a single collision or finishes the chain it started.
~ Emily
Top comments (0)