ASTEROID_COLLISIONS

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& arr) {
        int n = arr.size();

        vector<int> ans;

        stack<int> st;


        for(int i = 0; i < n; ++i) {
            if(arr[i] > 0) {
                st.push(arr[i]);
            }

            else {
                while(!st.empty() and arr[i] < 0 and st.top() < abs(arr[i])) {
                    st.pop();
                }
                if(st.empty()) {
                    ans.push_back(arr[i]);
                }
                else if(st.top() == abs(arr[i])) {
                    st.pop();
                }
            }
        }

        //reverse stack and push to ans

        stack<int> rev;


        while(!st.empty()) {
            rev.push(st.top());
            st.pop();
        }

        while(!rev.empty()) {
            ans.push_back(rev.top());
            rev.pop();
        }
        // reverse(ans.begin(), ans.end());
        return ans;
    }
};