Problem Explanation

We are given an array of ints where the absolute value of each int represents the size, and the sign its direction. Positive values are moving to the right and negative ones are moving to the left. All asteroids move at the same speed.

Our task is to determine the final arrangement of asteroids after all collisions have resolved. In a collision, if two asteroids are of the same size, no matter their direction, they explode and disappear. If they are of different sizes, the smaller one will explode and the larger one will continue its journey. Asteroids moving in the same direction never collide.

Let's walk through the first example in the problem description.

Problem Example

Let's start with this array asteroids = [5, 10, -5].

The 10 and -5 will collide, as the 10 is positive (rightward), and -5 is negative (leftward). The 10 is of larger absolute value, thus the -5 is destroyed and disappears. The array then becomes asteroids = [5, 10].

Since the remaining asteroids, 5 and 10, are both moving right, they will never collide. This results in the final output of [5, 10].

Approach

We can solve this using a stack. This is because a stack represents the 'ongoing path' of the asteroids. We keep adding asteroids to the stacks as long as they are moving in the same direction. As soon as we find an asteroid that is moving in the opposite direction, we start checking it with the elements of the stack (the ones that are in its path on the opposite direction).

If the incoming asteroid is smaller, it gets destroyed immediately. If it's larger, then it destroys the asteroid on the stack and this continues until we find an asteroid that can destroy it or until it destroys all asteroids, in which case it gets added to the stack.

Python Solution

1
2python
3class Solution:
4    def asteroidCollision(self, asteroids):
5        stack = []
6        for a in asteroids:
7            if a > 0:
8                stack.append(a)
9            else:
10                while stack and stack[-1] > 0 and stack[-1] < -a:
11                    stack.pop()
12                if not stack or stack[-1] < 0:
13                    stack.append(a)
14                elif stack and stack[-1] == -a:
15                    stack.pop()
16        return stack

Java Solution

1
2java
3public class Solution {
4    public int[] asteroidCollision(int[] asteroids) {
5        Stack<Integer> stack = new Stack<>();
6        for (int i = 0; i < asteroids.length; i++) {
7            if (asteroids[i] > 0) {
8                stack.push(asteroids[i]);
9            }
10            else {
11                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroids[i]) {
12                    stack.pop();
13                }
14                
15                if (stack.isEmpty() || stack.peek() < 0) {
16                    stack.push(asteroids[i]);
17                } else if (stack.peek() == -asteroids[i]) {
18                    stack.pop();
19                }
20            }
21        }
22        int[] res = new int[stack.size()];
23        for (int i = stack.size() - 1; i >= 0; i--) {
24            res[i] = stack.pop();
25        }
26        return res;
27    }
28}

JavaScript Solution

1
2javascript
3var asteroidCollision = function(asteroids) {
4    let stack = [];
5    for(let i=0; i < asteroids.length; i++) {
6        let asteroid = asteroids[i];
7        
8        if (asteroid > 0) {
9            stack.push(asteroid);
10        } else {
11            while (stack.length && stack[stack.length-1] > 0 && stack[stack.length-1] < Math.abs(asteroid)) {
12                stack.pop();
13            }
14            
15            if (!stack.length || stack[stack.length-1] < 0) {
16                stack.push(asteroid);
17            } else if (stack[stack.length-1] === Math.abs(asteroid)) {
18                stack.pop();
19            }
20        }
21    }
22    return stack;
23};

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<int> asteroidCollision(vector<int>& asteroids) {
6        vector<int> stack;
7        for (int a : asteroids) {
8          if (a > 0){
9            stack.push_back(a);
10          }
11          else {
12            while (!stack.empty() && stack.back() > 0 && stack.back() < abs(a))
13              stack.pop_back();
14            if (stack.empty() || stack.back() < 0)
15              stack.push_back(a);
16            else if (stack.back() == abs(a))
17              stack.pop_back();
18          }
19        }
20        return stack;
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int[] AsteroidCollision(int[] asteroids) {
5        Stack<int> stack = new Stack<int>();
6        foreach (int a in asteroids) {
7            if (a > 0) {
8                stack.Push(a);
9            } else {
10                while (stack.Count != 0 && stack.Peek() > 0 && stack.Peek() < -a) {
11                    stack.Pop();
12                }
13                
14                if (stack.Count == 0 || stack.Peek() < 0) {
15                    stack.Push(a);
16                } else if (stack.Peek() == -a) {
17                    stack.Pop();
18                }
19            }
20        }
21        
22        int[] result = new int[stack.Count];
23        for (int i = stack.Count - 1; i >= 0; i--) {
24            result[i] = stack.Pop();
25        }
26        return result;
27    }
28}

Explanation of the Code

Python

In Python, we first create an empty stack. We now start a loop where we visit each asteroid one by one. If the asteroid is moving to the right, we add it to the stack. If it's moving to the left, we start a while loop where we pop right moving asteroids from the stack as long as they are smaller than the current left moving asteroid. If we find any right moving asteroid that is equal in size, we pop it and break the loop. If we find a larger one, we break the loop without popping. After the while loop, if the current asteroid is larger than all right movers or if it's the first left mover, we add it to the stack.

Finally, when we have visited all asteroids, we return the stack as the answer.

Java

In Java, we do things a bit differently. We first push all right moving asteroids onto the stack. Then, for the left moving asteroids, we pop from the stack as long as we can find smaller right movers.

However, here, we also check if the top of the stack contains a left mover or if the stack is empty. In either case, we push the current asteroid to the stack. Else, we know that the top of the stack is a right mover that is bigger or equal to the absolute value of the current asteroid, which means the current asteroid will be destroyed and we don't do anything.

In the end, we convert the stack to an array and return this array as the answer.

JavaScript

In JavaScript, the logic is exactly the same as Python. The only difference is that instead of stack[-1], we use stack[stack.length-1] because JavaScript does not allow negative indices.

The rest of the code remains the same.

C++

The C++ implementation is similar to the Python version. The primary difference is instead of using a list as stack, we use a vector.

Also, to get the last element of the vector, we use stack.back(). To remove it, we use stack.pop_back(). Otherwise, the program flow is exactly the same as the Python version.

C#

In C#, we use System.Collections.Generic for using the Stack class. We initialize a new stack and push the asteroids moving to the right onto the stack.

Then we pop right-movers which are smaller than the current left-mover. If the stack becomes empty or a left mover is found on top of the stack, we push the current left mover onto the stack.

We also check if the top of the stack has an equal but right mover, if so we pop the asteroid from the stack. In the end, we convert the stack to an array and return it as the result.