0735.Asteroid Collision

Link: 735. Asteroid Collision - Medium
Track:

Question

Restate the problem

• Given an integer array asteroids where sign = direction and abs = size, simulate collisions.
• Return the final asteroid sequence after all possible collisions.

---

Method 1: Remove only one asteroid per pass, Time is O($n^2$)
Method 2: Stack

Method

Approach

• Maintain a stack of asteroids that are “settled” so far.
• For each incoming asteroid a:
  • If a is moving right (a > 0): it can’t collide with previous left-movers behind it → push
  • If a is moving left (a < 0): it may collide with previous right-movers on stack top
    • While stack top is a right-mover (>0) and a still alive:
      • compare sizes, pop smaller right-movers
      • if equal, pop and kill a
      • if stack top bigger, kill a
  • If a survives, push it

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Edge Case

• If no asteroids, return []

Code

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for a in asteroids:
            alive = True
 
            while alive and stack and stack[-1] > 0 and a < 0:
                if stack[-1] < abs(a):
                    stack.pop()
                    continue
                elif stack[-1] == abs(a):
                    stack.pop()
                    alive = False
                else: # stack[-1] > abs(a)
                    alive = False
            
            if alive:
                stack.append(a)
            
        return stack

---

History

• Feb-22-2026 Hinted,
• Jan-20-2026 Peeked, need aliveflag