Asteroid Collision : LeetCode:735

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.

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 <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Approach

Process each integer value from left to right.

Utilise a stack to store the results.

If the encountered asteroid value is positive, add it to the stack since it won’t collide with existing positive values in the stack.

If the new asteroid value is negative, remove all positive asteroids smaller than the new value from the stack.

Add the new value to the stack if it is empty or if the last element in the stack is also negative (processed in the previous run).

If there are two opposing asteroids of the same size, remove the last one.

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
         Stack<Integer> stk =new Stack<>();
        int n=asteroids.length;
    
        for(int i=0;i<n;i++) {
          
            //if positive push into the stack
            if(asteroids[i] >  0){
              stk.push(asteroids[i]);
            }
            //if negative 
            else{
               while(stk.size()>0 && stk.peek() >0 && stk.peek() < -asteroids[i]) {
                   stk.pop();
               } 
               if(stk.size() >0 && stk.peek() == -asteroids[i]){
                   stk.pop();
               }
               else if(stk.size() > 0 && stk.peek() > -asteroids[i] ){
                   
               }else{ 
                   stk.push(asteroids[i]);
               }
            }
        }
        int[] ans=new int[stk.size()];
        int i = ans.length-1;
        while(i>=0){
            ans[i]=stk.pop();
            i--;
        }
        return ans;
    }
}

Time Complexity:

The algorithm exhibits a time complexity of O(n), with n denoting the quantity of asteroids.

Space Complexity:

The algorithm also has a space complexity of O(n), where n represents the total number of asteroids.

#dsa#algo#coding#developers#happy_learning