Algorithm

Asteroid Collision

Monotonic Stack Pattern

Asteroid Collision

Simulate asteroid collisions where absolute value is size and sign is direction (+ right, - left).

CONSTRAINTS
  • 2 <= asteroids.length <= 10⁴
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0
EXAMPLE 1
Input: asteroids = [5,10,-5]
Output: [5,10]
10 and -5 collide, 10 wins. 5 and 10 move right.
EXAMPLE 2
Input: asteroids = [10,2,-5]
Output: [10]
2 and -5 collide, -5 wins. Then 10 and -5 collide, 10 wins.
EXAMPLE 3
Input: asteroids = [8,-8]
Output: []
Both moving toward each other with same size. Both are destroyed.
Do asteroids in the same direction collide?
No. They maintain a constant speed and distance. Only asteroids moving toward each other (+) then (-) can collide.
What if there are only negative asteroids?
They all survive. Since they are moving left, and there are no positive asteroids to their left to hit them, they never encounter any obstacles.

Asteroid collisions only happen when two asteroids move toward each other. In this universe, that only happens when a Right-moving (+) asteroid is to the left of a Left-moving (-) one.

Think of it as a line of Defenders (Right-moving) waiting for an incoming Attacker (Left-moving). When an Attacker arrives, it must pass through a Gauntlet of every Defender it encounters.

The Gauntlet

We use a Stack to track our current line of survivors.
1. Moving Right: These asteroids are "Defenders." They never collide with each other, so they just join the end of the line (Stack).
2. Moving Left: This asteroid is an "Attacker." It looks at the very last Defender in the line (the Stack Top):
- If the Attacker is bigger: It smashes the Defender (Pop) and moves on to the next one in line. It keeps going until it's destroyed or the line is empty.
- If they are equal: Both are annihilated. The Defender leaves the line, and the Attacker disappears.
- If the Defender is bigger: The Attacker is immediately destroyed. The line remains unchanged.
3. Breakthrough: If an Attacker smashes through the entire line and finds the universe empty (or only finds other Left-moving survivors), it becomes a permanent survivor and joins the Stack itself.

Code Blueprint
text
stack = []

FOR asteroid in asteroids:
    IF asteroid > 0:
        stack.PUSH(asteroid)
    ELSE:
        // Attacker arrives! Resolve collisions
        WHILE stack is NOT empty AND stack.PEEK() > 0 AND stack.PEEK() < ABS(asteroid):
            stack.POP() // Defender destroyed
        
        IF stack is NOT empty AND stack.PEEK() == ABS(asteroid):
            stack.POP() // Both destroyed
        ELSE IF stack is empty OR stack.PEEK() < 0:
            stack.PUSH(asteroid) // Attacker survives
        // ELSE: stack.PEEK() > ABS(asteroid), Attacker is destroyed (do nothing)

RETURN stack
Worked Example:[10, 2, -5]
0
10
Top
Scan 10: Right-moving (> 0). Push onto stack. Stack = [10].
0
10
1
2
Top
Scan 2: Right-moving (> 0). Push onto stack. Stack = [10, 2].
0
10
Top
Scan -5: Left-moving (< 0). Collision with 2! Compare sizes: |-5| > |2|. Asteroid 2 is popped and destroyed. -5 continues.
0
10
Top
Collision with 10! Compare sizes: |10| > |-5|. Asteroid -5 is destroyed. Stack remains [10]. Final result: [10].
Interactive Strategy Visualization
COLLISION PHYSICS INSIGHT

Stack-based multi-collision chain reaction

10
Empty space. 10 (Right) enters the void.

Mental Model

  • Stack as History: The stack tracks asteroids currently flying Right (+). They are the potential targets for incoming Left (-) asteroids.
  • Cascading Collisions: A single incoming (-) asteroid can trigger a chain reaction, destroying multiple (+) asteroids in the stack until it meets its match or survives.
  • Momentum: (-, +) never collide because they are already moving away from each other. (+, -) is the only collision case.
SIMULATION LOGSTEP 1/8
Empty space. 10 (Right) enters the void.
RULES

Interaction Physics

1. Positive (+) flies Right. 2. Negative (-) flies Left. 3. Larger Mass survives. 4. If Equal Mass, both are destroyed. 5. Only Right-Left pairs collide.

O(N²) Re-simulate Until Stable
→
O(N) Stack Simulation