LeetCode #735 Medium

Asteroid Collision

Asteroids move left or right by sign, with magnitude giving size. Equal sizes destroy both; otherwise the smaller is destroyed. Return the final state.

stackarraysimulation

Open on LeetCode ↗

02

Intuition

💡

Writing if st and st[-1] > 0 and st[-1] < -a: st.pop() looks like it handles a collision, but it only fights one round: a big left-mover that should plow through three smaller right-movers in a row stops after destroying the first one and then gets pushed on top of a survivor it should have destroyed too. The fix is while, not if — a collision only ever happens between a right-mover already in flight and a left-mover arriving behind it, and the left-mover keeps fighting backwards through the stack until it dies, ties out, or clears everything in its way and lands.

03

Approach

1

Identify the only collision case

Two right-movers never meet, nor do two left-movers, and a left-mover followed by a right-mover diverges. The single colliding configuration is a positive value on the stack with a negative value arriving — checking that pair is the whole simulation.

2

Fight backwards while the collision holds

For an incoming negative asteroid, loop while the stack top is positive and smaller in magnitude: pop it, since the incoming one wins and continues. If the top is larger, the incoming asteroid is destroyed and you stop without pushing. If magnitudes are equal, pop the top and destroy the incoming one too.

3

Push the survivor

If the incoming asteroid survived every fight, push it. The bug to watch is reaching for if instead of while in the collision loop above — with if, a size-10 left-mover meeting [3, 4, 5] on the stack only pops the 5, then gets appended on top of the still-alive 3 and 4, leaving three asteroids where physically only one should remain. Use a flag or a for/else to distinguish surviving from being destroyed. Each asteroid is pushed and popped at most once, so the whole thing is O(n) time and O(n) space.

04

Solution & live demo

python

▶1class Solution:
▶2    def asteroidCollision(self, asteroids):
▶3        st = []
▶4        for a in asteroids:
▶5            alive = True
▶6            while alive and a < 0 and st and st[-1] > 0:
▶7                if st[-1] < -a:
▶8                    st.pop()
▶9                elif st[-1] == -a:
▶10                    st.pop()
▶11                    alive = False
▶12                else:
▶13                    alive = False
▶14            if alive:
▶15                st.append(a)
▶16        return st

05

Edge cases

All moving the same direction

No collisions ever occur; the input is returned unchanged.

Equal magnitudes colliding

Both are destroyed — remember to pop and not push.

A left-mover with an empty stack

Nothing can hit it, so it is pushed directly.

One large asteroid clearing several

The while loop pops repeatedly, which is why it must be a loop rather than a single if.

06

Complexity

Time

O(n)

Space

O(n)

Each asteroid enters and leaves the stack at most once.