Simulate collisions between moving asteroids and return the survivors in order.
Asteroid Collision
You are given an array of integers representing asteroids in a straight line. The absolute value of each integer is the asteroid's size, and the sign indicates its direction:
> 0means the asteroid is moving to the right< 0means the asteroid is moving to the left
All asteroids move at the same speed. When two asteroids moving in opposite directions meet, they collide:
- The smaller asteroid is destroyed
- If both are the same size, both are destroyed
- Asteroids moving in the same direction never collide
Determine the state of the asteroids after all possible collisions have occurred.
Input Format
- One integer array
asteroids - Each value is a non-zero integer
abs(asteroids[i])is the size and the sign is the direction
Output Format
Return an array containing the asteroids that remain after all collisions, in their original relative order.
Constraints
1 <= asteroids.length <= $10^{5}$-1000 <= asteroids[i] <= 1000asteroids[i] != 0
Example 1
Input
asteroids = [5,10,-5]
Output
[5,10]
Explanation
-5 collides with 10 and is destroyed. 5 and 10 continue moving right.
Example 2
Input
asteroids = [8,-8]
Output
[]
Explanation
The two asteroids are the same size, so both are destroyed.
Show 1 more example
Example 3
Input
asteroids = [10,2,-5]
Output
[10]
Explanation
2 is destroyed by -5, then -5 is destroyed by 10.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.