Problem
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 meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet. (link)
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Constraints:
2 <= asteroids.length <= 10<sup>4</sup>-1000 <= asteroids[i] <= 1000asteroids[i] != 0
Solution
Imagine we have a bunch of asteroids floating in space, all lined up in a row. Each asteroid has a size (which can be positive or negative) and a direction of movement (left or right). When these asteroids collide, interesting things happen. Let’s break down the cases you’ve provided:
Case 1: [-4, 4]
The asteroid with size -4 moves left, and the one with size 4 moves right.
Since they’re moving away from each other, there’s no collision. Phew! Both asteroids continue on their merry way.
Case 2: [4, -4]
The positive asteroid (size 4) moves right, and the negative asteroid (size -4) moves left.
They collide head-on! The result? Both asteroids get destroyed. It’s like cosmic bumper cars.
Case 3: [5, -4]
The positive asteroid (size 5) moves right, and the negative asteroid (size -4) moves left.
Collision alert! The negative asteroid gets obliterated, but the positive one keeps going. So we’re left with just the size 5 asteroid.
Case 4: [3, -4]
The positive asteroid (size 3) moves right, and the negative asteroid (size -4) moves left.
Collision time! The size 3 asteroid bites the dust, while the negative one survives. Only the size -4 asteroid remains.
Algorithm Explanation
Sequential Iteration:
- Imagine we’re observing the asteroids one by one as they start their movement. It’s like watching a cosmic parade where each asteroid gets its turn.
Using a Stack:
We’ll employ a stack to keep track of the “alive” asteroids. This stack will contain asteroids that haven’t collided yet.
As we iterate through the asteroids, we’ll make decisions based on their sizes and directions.
Collision Logic:
When we encounter an asteroid during iteration:
If it’s a positive-sized asteroid (moving right), we add it to the stack. Why? Because we don’t know if there’s an incoming negative asteroid.
If it’s a negative-sized asteroid (moving left), we check for collisions:
While the stack isn’t empty and the top asteroid is positive-sized:
Compare their absolute sizes.
If the negative asteroid is larger, it destroys the positive asteroid (pop from the stack).
If the positive asteroid is larger or equal, the negative asteroid gets destroyed (no change to the stack).
If the stack is empty or the top asteroid is negative-sized, the negative asteroid survives and joins the stack.
Bottom Line:
The collision happens with the top element of the stack (if it’s positive) and the incoming negative asteroid.
The bottom positive asteroid remains untouched because it’s shielded by the stack.
Time - O(2 * n)
Space - O(n)
The time complexity is O(2*n) because we iterate through the entire array of asteroids, which takes (n) iterations. Additionally, we can pop out a maximum of (n) asteroids from the stack, and each pop operation occurrs only once.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for(int num: asteroids){
if(num>0) stack.push(num);
else{
while(!stack.empty() && stack.peek()>0 && stack.peek()<Math.abs(num)){
stack.pop();
}
if(!stack.empty() && stack.peek()>0 && stack.peek()==Math.abs(num)){
stack.pop();
}
else if(stack.empty() || stack.peek()<0){
stack.push(num);
}
}
}
//convert to array
int[] ans = new int[stack.size()];
int i = stack.size()-1;
while(!stack.empty()){
ans[i] = stack.pop();
i-=1;
}
return ans;
}
}