735. Asteroid Collision

[songyy5517]

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.

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 This problem is to find out all the remaining stars after collision. So first we have to figure out all the cases of collision. From the description, we can infer that collision would happen only when the current star is less than 0, and the preceding star is greater than 0. Under this circunstance, there are three cases. If their sum is 0, that is, their absolute value is the same, then both of them will explode. If their sum is less than 0, that is, the size of the current star is heavier, only the preceding start will explode. Also, if the sum is greater than 0, only the current star will explode. Based on this, a straightforward idea is that we can define a stack first. Then loop through the whole array, we consider both the current element and the top element in the stack. If they would collide, then we remove the smaller stars from the stack; otherwise, we add the alive star into the stack.

[songyy5517]

Approach: Stack

1. Exception handling;
2. Define variables:
   • stack: stores the alive asteroids;
   • alive: deternmines whether the current asteroid would be alive;
3. Loop through the whole array; （1）Set alive to true; （2）If the current asteroid would collide with the top element in the stack, then perform the following steps until no collision occurs:
   • If their sum is 0, then remove the top element from the stack, and set alive to false;
   • If their sum is less than 0, then just remove the top element from the stack;
   • If their sum is greater than 0, set alive to false; （3）If alive is true, add the current element to the stack.
4. Convert the stack to an int array, and return;

Complexity Analysis

• Time complexity: $O(N)$ , looping through the whole array costs the time of $O(N)$ ;
• Space complexity: $O(N)$ , addtionally define a stack which takes up $O(N)$ space.

[songyy5517]

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        // Intuition: Stack.
        // 1. Exception Handling
        if (asteroids == null || asteroids.length == 0)
            return new int[0];

        // 2. Define Stack
        Stack<Integer> stack = new Stack();
        Boolean alive = true;    // indicates whether the current star is alive

        // 3. Iterate over the array
        for (int i = 0; i < asteroids.length; i++){
            alive = true;

            // Collison
            while (alive && !stack.isEmpty() && (stack.peek() > 0 && asteroids[i] < 0)){
                // Both collide
                if (stack.peek() + asteroids[i] == 0){
                    stack.pop();
                    alive = false;
                }
                // cur collides
                else if (stack.peek() + asteroids[i] > 0)
                    alive = false;

                // Top collides
                else 
                    stack.pop();

            }

            if (alive)
                stack.push(asteroids[i]);
        }

        // 4. Stack -> Array
        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; i--)
            res[i] = stack.pop();

        return res;
    }
}

[songyy5517]

2024/5/22