Asteroid Collision
Medium · Stack & Strings · Array · Stack · Simulation
Problem
You are given an array asteroids describing asteroids lined up in a row. The absolute value of each number is the asteroid's size, and its sign gives its direction: positive moves right, negative moves left. All asteroids travel at the same speed.
When two asteroids meet, the smaller one explodes; if they are the same size, both explode. Asteroids moving in the same direction never meet, and a left-mover that is left of a right-mover is moving away from it.
Return the asteroids that remain after all collisions, in their original order.
Examples
Input: asteroids = [6,3,-4] Output: [6]
-4 destroys 3, then is itself destroyed by the larger 6.
Input: asteroids = [2,-2,5,-7] Output: [-7]
2 and -2 destroy each other, and -7 destroys 5.
Input: asteroids = [-3,4] Output: [-3,4]
-3 moves left and 4 moves right, so they never meet.
Constraints
- 2 <= len(asteroids) <= 10^4
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
Approaches
- Baseline: resolve the first collision, repeat — time O(n²), space O(n)
Follow-up
What if, instead of exploding, the larger asteroid keeps flying with its size reduced by the smaller one? The same stack works: the winner is updated in place instead of left as it is. The second use case below asks exactly that.
Related problems
Start free on Cariara · Coding problems · System design studio
