An array asteroids lists asteroids in a row. The absolute value is the size, and the sign is the direction: positive moves right, negative moves left. All move at the same speed. When a right mover meets a left mover, the smaller one explodes; if they are the same size, both explode. Two asteroids moving the same way never meet. Return the asteroids that survive, in order.
- 2 <= asteroids.length <= 10^4
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force simulates step by step, scanning for any adjacent pair +a, -b and resolving it until nothing changes: O(n^2). The key observation is that a new left mover always meets the nearest surviving right mover first, which is the most recent one we kept. That is a stack. Right movers are pushed. A left mover fights the stack top while the top is positive: it destroys smaller tops, dies against bigger ones, and both vanish when sizes match. If it clears all right movers, it is safe and gets pushed.
Algorithm
- Create an empty stack of survivors.
- For each asteroid
a: ifa > 0, push it and continue. - Otherwise, while the top is positive and smaller than
-a, pop it. - If the top is positive and equal to
-a, pop it and dropa. If the top is positive and bigger, dropa. - If
asurvived (stack empty or top negative), push it. Return the stack.
O(n)Space: O(n)[-2,-1], never collides: both move left. Also [-2,1] has no collision, since they move apart. Only the pattern "positive then negative" fights.class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for a in asteroids: alive = True # Only a left mover (a < 0) can hit right movers on the stack. while alive and a < 0 and stack and stack[-1] > 0: if stack[-1] < -a: stack.pop() # the right mover explodes, keep fighting else: if stack[-1] == -a: stack.pop() # both explode alive = False # a explodes if alive: stack.append(a) return stack