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.

&nbsp;
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.


&nbsp;
Constraints:


	2 &lt;= asteroids.length &lt;= 104
	-1000 &lt;= asteroids[i] &lt;= 1000
	asteroids[i] != 0


class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for a in asteroids:
            while stack and stack[-1] > 0 > a:
                if stack[-1] < abs(a):
                    stack.pop()
                    continue
                elif stack[-1] == abs(a):
                    stack.pop()
                break # this means asteroid must be destroyed (not add to stack in else statement below)
            else:
                stack.append(a)
        
        return stack
/*
0. Start iterating over the asteroid one by one.
1. If the stack is not empty, and its top > 0 (right moving asteroid) and current asteroid < 0 (left moving), we have collision.
2. Pop all the smaller sized right moving asteroids (i.e. values > 0 but lesser than absolute value of left moving asteroid i.e. abs(<0))
3. Now that we have taken care of collisions with smaller size right moving asteroids, we need to see if there's a same sized right moving asteroid. If yes, just remove that one as well. Do not add the current left moving asteroid to the stack as it will be annihilated by the same sized right moving asteroid. Continue to the next iteration, we are done handling with this left moving asteroid.
4. If we are here, we still need to deal with the current left moving asteroid. Check the top of the stack as to what is there on top. If its a larger sized right moving asteroid, it will annihilate this current left moving asteroid. So Continue to the next iteration, we are done handling with this left moving asteroid.
5. If we are here, it means the current asteroid has survived till now either because it did not meet any collisions or won in the collisions. In this case, push the asteroid on to the stack.
6. Convert the stack to an array in return it.

*/
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        //0. Start iterating over the asteroid one by one.
        for(int a : asteroids) {

            //1. If the stack is not empty, and its top > 0 (right moving asteroid) and current asteroid < 0 (left moving), we have collision.
            //2. Pop all the smaller sized right moving asteroids (i.e. values > 0 but lesser than absolute value of left moving asteroid i.e. abs(<0))
            while(!stack.isEmpty() && stack.peek() > 0 && a < 0 && stack.peek() < Math.abs(a)) {
                stack.pop();
            }

            //3. Now that we have taken care of collisions with smaller size right moving asteroids, we need to see if there's a same sized right moving asteroid. If yes, just remove that one as well. Do not add the current left moving asteroid to the stack as it will be annihilated by the same sized right moving asteroid. Continue to the next iteration, we are done handling with this left moving asteroid.
            if(!stack.isEmpty() && stack.peek() > 0 && a < 0 && stack.peek() == Math.abs(a)) {
                stack.pop();
                continue;
            }

            //4. If we are here, we still need to deal with the current left moving asteroid. Check the top of the stack as to what is there on top. If its a larger sized right moving asteroid, it will annihilate this current left moving asteroid. So Continue to the next iteration, we are done handling with this left moving asteroid.
            if(!stack.isEmpty() && stack.peek() > 0 && a < 0 && stack.peek() > Math.abs(a)) {
                continue;
            }

            //5. If we are here, it means the current asteroid has survived till now either because it did not meet any collisions or won in the collisions. In this case, push the asteroid on to the stack.
            stack.push(a);

        }

        //6. Convert the stack to an array in return it.
        int[] ans = new int[stack.size()];
        int i = stack.size() - 1;
        while(!stack.isEmpty()) {
            ans[i] = stack.pop();
            i--;
        }
        return ans;
    }
}
class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        
        vector<int>v;
        stack<int>s;
        
        for(auto x: asteroids){
            
            if(x > 0) s.push(x);
            
            else{
                
                // Case 1: whem top is less than x
                
                while(s.size() > 0 && s.top() > 0 && s.top() < -x){
                    s.pop();
                }
                
                // case 2 : when both of same size
                if(  s.size() > 0 && s.top()==-x) {
                    s.pop();
                }
                
                // case 3: when top is greater
                
                else if( s.size() > 0 && s.top() > -x ){
                   // do nothing
                }
                
                // case 4: when same direction 
                
                else{
                    s.push(x);
                }
            }
        }
        
        while(!s.empty()){
            v.push_back(s.top());
            s.pop();
        }
        
        reverse(v.begin(),v.end());
        
        return v;
    }
};
/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function(asteroids) {

    const s = [];
    for (let i = 0; i < asteroids.length; i++) {
        const a = asteroids[i];

        // Negative asteroids to the left of the stack can be ignored.
        // They'll never collide. Let's just add it to the answer stack and
        // move on. I consider this a special case.
        if ((s.length === 0 || s[s.length -1] < 0) && a < 0 ) {
            s.push(a);

        // If an asteroid a is positive (l to r), it may still collide with an
        // a negative asteroid further on in the asteroids array
        } else if (a > 0) {
            s.push(a);

        // a is negative. It can only collide with positive ones in
        // the stack. The following will keep on iterating
        // until it is dealt with.
        } else {
            const pop = s.pop();

            // positive pop beats negative a, so pick up pop
            // and re-add it to the stack.
            if (Math.abs(pop) > Math.abs(a)) {
                s.push(pop);

            // a has larger size than pop, so pop will get dropped
            // and we'll retry another iteration with the same
            // negative a asteroid and whatever the stack's state is.
            } else if (Math.abs(pop) < Math.abs(a)) {
                i--;
            // magnitude of positive pop and negative a are the same
            // so we can drop both of them.
            } else {
                continue;
            }
        }
    }

    // The stack should be the answer
    return s;

};
Asteroid Collision