Asteroid Collision
The key idea
A collision can only happen when a right-moving asteroid (positive) is immediately followed by a left-moving one (negative). Keep surviving asteroids on a stack: a new left-mover keeps blowing up the positive asteroids on top of the stack until it dies, ties out, or wins and is itself pushed. Anything else (a right-mover, or a left-mover with an empty/left-moving top) can never collide and is pushed directly.
Problem
You are given an array of integers asteroids representing asteroids in a row. For each asteroid, the absolute value is its size and the sign is its direction: positive means moving right, negative means moving left. Every asteroid moves at the same speed.
Find the state of the asteroids after all collisions. If two asteroids meet, the smaller one explodes. If both are the same size, both explode. Two asteroids moving in the same direction will never meet.
Constraints
- 2 <= asteroids.length <= 10^4
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
Examples
Input: asteroids = [5,10,-5]
Output: [5,10]
Input: asteroids = [8,-8]
Output: []
Input: asteroids = [10,2,-5]
Output: [10]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization