DAY 48 - Asteroid Collision

Hey everyone! Welcome back to another day of problem-solving. It's day 48, and I'm still going strong on my quest for consistency. Today, We will be solving a problem using monotonic stack.

Question: 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 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.

Intuition:

• So the question is pretty easy to understand.
• Two elements if they have the opposite signs collide provided the positive sign comes first.
• (+) & (-) Collide!
• (-) + (+) do not collide!
• You can check this by assigning positive right direction and negative left direction.
• So we need to check what sign is the element we are currently taking so we can take the desired action upon it.
• Next we will push the elements into the stack. If the top element of the stack is positive and the current element is positive or top is negative and element to be pushed is positive or negative we can simply push that onto the stack.
• Otherwise we will perform a collision and we will take the one with greater absolute value.
• We will pop stack elements one by one and add them to a list which will be our answer.

Algorithm:

1. Creating the Stack and Checking Collisions:

The code starts by creating an empty stack (st) to simulate the asteroid collisions. The stack will store the remaining asteroids that have not collided yet.

It then iterates over each asteroid in the input vector a.
For each asteroid, the code performs the following checks:

a. If the stack is empty, or the top of the stack is negative (indicating an asteroid moving to the left) and the current asteroid is positive (indicating an asteroid moving to the right), or both asteroids have the same direction (positive or negative), the current asteroid can safely move forward, and it is pushed onto the stack.

b. Otherwise, if the current asteroid is positive and the top of the stack is negative, or the absolute value of the current asteroid is greater than the absolute value of the top of the stack, it means there is a collision.

c. In the case of a collision, the while loop is used to check and resolve possible collisions with the top of the stack. It continues until either there are no asteroids left in the stack, or the top asteroid survives (its absolute value is greater than the absolute value of the current asteroid).

2. Returning the Result:

• After simulating all the asteroid collisions, the remaining asteroids in the stack represent the final state after all possible collisions.
• The code then constructs a new vector ans to store the state of the remaining asteroids in the correct order.
• It pops the asteroids from the stack and stores them in reverse order in the ans vector.
• Finally, the ans vector is returned as the result, indicating the state of the remaining asteroids after all possible collisions.

Code:

bool samesign(int x,int y){
       if(x<0&&y<0)
       return true;
       else if(x>0&&y>0)
       return true;
       return false;
   }
    vector<int> asteroidCollision(vector<int>& a) {
        int n=a.size();
        stack<int>st;
          for(int i=0;i<n;i++){
            if(st.size()==0 || (st.top()<0 && a[i]>0) || samesign(st.top(),a[i])){
                st.push(a[i]); 
            }else{
                while(st.size()>0 && st.top()>0 && st.top() < abs(a[i])) st.pop();

                if(st.size()==0 || st.top()<0){
                    st.push(a[i]);
                }else if(st.top() == abs(a[i])){
                    st.pop(); 
                }
            }
        }

        vector<int> ans(st.size());
        int i=st.size()-1;
        while(!st.empty()){
            ans[i]=st.top();
            i--;
            st.pop();
        }
        return ans;
    }

Complexity Analysis:

Time: O(2N)
Space: O(N)

Thanks for reading. Feedback is highly appreciated!