We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space.

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.

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

• Iterate over the asteroids from left to right; for each asteroid do the following:

• i. Initialize a boolean flag to true. We will use this flag later to determine if we should store this asteroid in the stack or if it will explode.

• ii. If there is an asteroid in the stack and the asteroid on the top of the stack can collide with this asteroid, then we have some options here.

• a. If the asteroid is bigger than the asteroid on the top, then this asteroid on the top will explode, and we will pop it from the stack.

• b. If the asteroid has the same size as the asteroid on the top, then both will explode. Hence we will pop it from the stack; also, we will mark flag as false because this asteroid will also explode, and hence we won't save it into the stack.

• c. If the asteroid is smaller than the asteroid on the top, then the asteroid on the top will not explode, so we will not pop it. But the asteroid will explode and thus we will mark flag as false.

• iii. If flag is true, add the asteroid to the stack.

• Add the asteroids from the stack into the list remainingAsteroids in the reverse order.

• Return remainingAsteroids.

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> st = new Stack<>();
        for(int i=0;i<asteroids.length;i++){
            boolean flag = true;
            // If the top asteroid in the stack is smaller, then it will explode.
                // Hence pop it from the stack, also continue with the next asteroid in the stack.
            while(!st.isEmpty() && st.peek()>0 && asteroids[i] < 0){
                if(Math.abs(st.peek())<Math.abs(asteroids[i])){
                    st.pop();
                    continue; 
                      // If both asteroids have the same size, then both asteroids will explode.
                // Pop the asteroid from the stack; also, we won't push the current asteroid to the stack.
                }else if(Math.abs(st.peek())==Math.abs(asteroids[i])){
                    st.pop();
                }
                                // If we reach here, the current asteroid will be destroyed
                // Hence, we should not add it to the stack
                flag = false;
                break;
            }
            if(flag){
                st.push(asteroids[i]);
            }
        }
      // Add the asteroids from the stack to the vector in the reverse order.
        int[] res = new int[st.size()];
        for(int i=st.size()-1;i>=0;i--){
            res[i]=st.pop();
        }
        return res;
    }
}

Here, N is the number of asteroids in the list.

Time complexity: O(N).

We iterate over each asteroid in the list, and for each asteroid, we might iterate over the asteroids we have in the stack and keep popping until they explode. The important point is that each asteroid can be added and removed from the stack only once. Therefore, each asteroid can be processed only twice, first when we iterate over it and then again while popping it from the stack. Therefore, the total time complexity is equal to O(N).

Space complexity: O(N).

The only space required is for the stack; the maximum number of asteroids that could be there in the stack is N when there is no asteroid collision. The final list that we return, remainingAsteroids, is used to store the output, which is generally not considered part of space complexity. Hence, the total space complexity equals O(N).