Problem
Given an integer array asteroids, where each value represents an asteroid moving in a one-dimensional space, the absolute value represents its size and the sign represents its direction. A positive value moves to the right, while a negative value moves to the left.When two asteroids collide, the smaller asteroid is destroyed. If both have the same size, both are destroyed. Asteroids moving in the same direction never collide.
Return the state of the asteroids after all collisions.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
asteroids = [5,10,-5]Output
[5,10]Example 2
Input
asteroids = [8,-8]Output
[]Solution
This solution uses a Stack to simulate the asteroid collisions. A collision can only occur when a positive asteroid is moving to the right and a negative asteroid is moving to the left. Therefore, when processing a negative asteroid, we compare it with the positive asteroid at the top of the stack.If the top asteroid is smaller, it is removed and the collision continues with the next asteroid. If both asteroids have the same size, the top asteroid is removed and the current asteroid is also destroyed. If the top asteroid is larger, the current asteroid is destroyed.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for (int asteroid : asteroids) {
boolean destroyed = false;
while (!stack.isEmpty() && asteroid < 0 && stack.peek() > 0) {
if (stack.peek() < -asteroid) {
stack.pop();
} else if (stack.peek() == -asteroid) {
stack.pop();
destroyed = true;
break;
} else {
destroyed = true;
break;
}
}
if (!destroyed) {
stack.push(asteroid);
}
}
int[] result = new int[stack.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return result;
}
}Complexity
Each asteroid is pushed onto and removed from the stack at most once, so the time complexity isO(n), where n is the number of asteroids.
The stack can contain up to n asteroids, so the extra space complexity is
O(n).
