Asteroid Collision

---

Asteroid Collision: 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.

---

Constraints:

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

---

Try this Problem on your own or check similar problems:

1. Can Place Flowers
2. Destroying Asteroids
3. Count Collisions on a Road

Solution:

Java

public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> s = new Stack<>();
    for(int i = 0; i < asteroids.length; ++i){
        int asteroid = asteroids[i];
        boolean currentExploded = false;
        while(!s.isEmpty() && (asteroid < 0 && s.peek() > 0) && Math.abs(s.peek()) <= Math.abs(asteroid)){
            if(Math.abs(s.peek()) == Math.abs(asteroid)){
                s.pop();
                currentExploded = true;
                break;
            }
            s.pop();
        }

        if((s.isEmpty() || !(s.peek() > 0 && asteroid < 0)) && !currentExploded) s.push(asteroid);
    }

    int[] result = new int[s.size()];
    int writer = s.size() - 1;
    while(writer >= 0){
        result[writer--] = s.pop();
    }

    return result;
}

JavaScript

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
  const stack = [];
  for (let i = 0; i < asteroids.length; i++) {
    const asteroid = asteroids[i];
    let currentExploded = false;
    while (
      stack.length &&
      asteroid < 0 &&
      stack[stack.length - 1] > 0 &&
      Math.abs(stack[stack.length - 1]) <= Math.abs(asteroid)
    ) {
      if (Math.abs(stack[stack.length - 1]) === Math.abs(asteroid)) {
        stack.pop();
        currentExploded = true;
        break;
      }
      stack.pop();
    }

    if (
      (!stack.length || !(stack[stack.length - 1] > 0 && asteroid < 0)) &&
      !currentExploded
    ) {
      stack.push(asteroid);
    }
  }

  return stack;
};

Python

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for asteroid in asteroids:
            current_exploded = False
            while stack and asteroid < 0 and stack[-1] > 0 and abs(stack[-1]) <= abs(asteroid):
                if abs(stack[-1]) == abs(asteroid):
                    stack.pop()
                    current_exploded = True
                    break
                stack.pop()

            if (not stack or not (stack[-1] > 0 and asteroid < 0)) and not current_exploded:
                stack.append(asteroid)

        return stack

C++

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
         vector<int> stack;
        for (int asteroid : asteroids) {
            bool currentExploded = false;
            while (!stack.empty() && asteroid < 0 && stack.back() > 0 && abs(stack.back()) <= abs(asteroid)) {
                if (abs(stack.back()) == abs(asteroid)) {
                    stack.pop_back();
                    currentExploded = true;
                    break;
                }
                stack.pop_back();
            }

            if ((stack.empty() || !(stack.back() > 0 && asteroid < 0)) && !currentExploded) {
                stack.push_back(asteroid);
            }
        }

        return stack;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

We have linear time and space complexity proportional to the length of input array. The stack seems like a natural choice for this problem since we're comparing the current element (asteroid) with the subarray of previous elements (each time popping them out in reverse order if the requirement is fulfilled). Since the positive asteroids move in right side, and negative in the left, we can only have collision when negative asteroid comes after the positive one asteroid < 0 && s.peek() > 0, so for each negative asteroid we discard any smaller (in absolute value) positive asteroids. We also track if we have an exact size, but opposite direction asteroid to our current one. Finally we push the asteroid if it hasn't exploded already !currentExploded (or if it's the first asteroid we're observing), and if we have any other scenario except for larger positive asteroid at the top of stack with a current smaller negative asteroid (in which case we have to discard asteroids, since we have an explosion). The scenarios that are valid are negative asteroid as our current one with previous negative on top of the stack, current and asteroid on top of the stack both positive, and negative asteroid on the top with positive one currently selected. We finally write to our result by popping each asteroid (not exploded) from the stack.