LeetCode 735 : Asteroid Collision

Description

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.

Get bytePudding’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

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.

Intuition

• Asteroids collide only the previous asteroid is positive (pointing right) and the following asteroid is negative (pointing left) -> Collide <-
• Therefore , lets first assume we store asteroid to a stack when an asteroid has positive sign

Let’s consider when asteroid has a negative sign

1. When we previously stored the positive value in a stack, It means it will collide

• (positive sign:stack ) => COLLIDE ≤ = (negative sign : asteroid )
• Check if the absolute value of asteroid is bigger than stack.peek(). If asteroid has bigger absolute value, remove top of stack (stack.pop()).
• Compare this till the stack value is positive

2. If stack is empty and asteroid has a negative sign , There’s no collide , So store it in a stack . Also if previous stack is negative and current asteroid is negative, it means no collide, So store it in a stack too

3. When both of elements have different signs and have same amount , it will collide . so remove it from a stack

class Solution {
    public int[] asteroidCollision(int[] asteroids) {

        Stack<Integer> st = new Stack();

        for(int i=0; i<asteroids.length; i++){
            if(asteroids[i] > 0){ // if asteroid is positive
                st.push(asteroids[i]);
            }else{ // when asteroid is negative

                while(st.peek() > 0 && !st.isEmpty() && Math.abs(asteroids[i]) > st.peek()){
                        st.pop(); // when absolute value of asteroid is bigger, remove
                }

                if(st.isEmpty() || st.peek() < 0){
                       st.push(asteroids[i]); 
                 // when stack is empty, store negative
                 // if the previous stack was negative , store in the stack (no collision)
                }

                if(asteroids[i] + st.peek() == 0){
                      st.pop();
                }

            }

        } // end-for


       int[] ans = new int[st.size()];
        int len = ans.length-1;

       for(int i=len; i>=0; i--){
            ans[i] = st.pop();
        }
      
        return ans;

  }
}

Time complexity of this algorithm takes O(n) because we are iterating over the asteroids array. meanwhile, stack calculation such as pop() and peek() only takes O(1) because we are check only the top of the stack. However in the worst case, we might insert and remove again which takes O(n). Therefore, the overal time complexity takes O(n)

Space complexity of this algorithm takes O(n) because in the worst case, all of the asteroids might stored in the stack where n is number of asteroids. Also the output array takes O(n) where n is the number of stacks. The total space complexity takes O(n)