Asteroid Collision
We are given an array asteroids of integers representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed. Find out the state of the asteroids after all collisions. If two asteroids collide, the larger one will remain, and the smaller one will be destroyed. If both are the same size, they will both be destroyed.
Constraints:
- 1 <= asteroids.length <= 10^4
- -10^5 <= asteroids[i] <= 10^5
Examples:
Input: [5,10,-5]
Output: [5,10]
Explanation: The first asteroid (size 5, moving right) and the second asteroid (size 10, moving right) collide. The second asteroid wins, so the first asteroid is destroyed. The second asteroid continues moving right. The third asteroid (size -5, moving left) and the second asteroid collide. The second asteroid wins, so the third asteroid is destroyed. The second asteroid continues moving right.
Solutions
Stack
We iterate through the asteroids array. For each asteroid, we check if the stack is not empty and the current asteroid is moving left and the top asteroid in the stack is moving right. If the top asteroid in the stack is smaller than the current asteroid, we pop the top asteroid from the stack and continue to the next iteration. If the top asteroid in the stack is equal to the current asteroid, we pop the top asteroid from the stack and break the loop. If the stack is empty or the current asteroid is moving right or the top asteroid in the stack is moving left, we push the current asteroid into the stack.
def asteroidCollision(asteroids):
stack = []; for asteroid in asteroids:
while stack and asteroid < 0 and stack[-1] > 0:
if stack[-1] < -asteroid:
stack.pop(); continue; elif stack[-1] == -asteroid:
stack.pop(); break; if not stack or asteroid > 0 or stack[-1] < 0:
stack.append(asteroid); return stackFollow-up:
What if the asteroids are moving at different speeds?
