735. Asteroid Collision

Source

Pointers:

Assume the asteroids index is there position in space and negative signed asteroids are moving towards 0th index and positive asteroids are moving towards lasts index. for example :-

1. [1,-2,10,-5]  

here, 1 and -2 will collide and 10 and -5 will collide but -2 and 10 wont collide.  
result -> [-2, 10]
2. [-4, 6]  
here, -4 will move left and 6 to its right and will never collide  
result -> [-4, 6]  
but in
3. [4, -6] 4 and -6 will collide and stronger asteroids will remain, as 6 is stronger than 4 , so -6 will remain resulting [-6].

Tip

-2 and -1 will move left side …where as 1,2 will move to right side…so there will be no collision
⇐- -2 , ⇐— -1 , 1 —⇒ , 2 —⇒ …hence no collision
so the - + pairs never collides as they move in opposite direction
note : +- will always collides
ex : if they have given input like 1,2,-2,-1 then the answer will be [] —⇒ 💥⇐----

Solution:

Intuition behind using stacks:

To solve this problem, we use a stack data structure that will help us manage the asteroid collisions efficiently. The stack is chosen because collisions affect the asteroids in a last-in, first-out manner: the most recently moving right asteroid can collide with the newly encountered left-moving one.

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(asteroids[0]);
 
        for(int i = 1; i < asteroids.length; i++){
            if(stack.peek() == null){
                stack.push(asteroids[i]);
                continue;
            }
            if((stack.peek() < 0 && asteroids[i] < 0) || (stack.peek() > 0 && asteroids[i] > 0)){
                // Same Direc
                stack.push(asteroids[i]);
            } else if ((stack.peek() > 0 && asteroids[i] < 0)){
                // Opp direc
                if (Math.abs(stack.peek()) < Math.abs(asteroids[i])){
                    stack.pop();
                    i--;
                } else if(Math.abs(stack.peek()) == Math.abs(asteroids[i])){
                    stack.pop();
                }
            } else if((stack.peek() < 0 && asteroids[i] > 0)){
                stack.push(asteroids[i]);
            }
        }
 
        int[] res = new int[stack.size()];
        int i = stack.size() - 1;
        while(!stack.isEmpty()){
            res[i] = stack.pop();
            i--;
        }
 
        return res;
 
    }
}