Code Implementation

class Solution:
    def asteroidCollision(self, asteroids):
        stack = []
        for ast in asteroids:
            while stack and ast < 0 < stack[-1]:
                if stack[-1] < -ast:
                    stack.pop()
                    continue
                elif stack[-1] == -ast:
                    stack.pop()
                break
            else:
                stack.append(ast)
        return stack
      

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> stack;
        for (int ast : asteroids) {
            bool destroyed = false;
            while (!stack.empty() && ast < 0 && stack.back() > 0) {
                if (stack.back() < -ast) {
                    stack.pop_back();
                    continue;
                } else if (stack.back() == -ast) {
                    stack.pop_back();
                }
                destroyed = true;
                break;
            }
            if (!destroyed) {
                stack.push_back(ast);
            }
        }
        return stack;
    }
};
      

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int ast : asteroids) {
            boolean destroyed = false;
            while (!stack.isEmpty() && ast < 0 && stack.peek() > 0) {
                if (stack.peek() < -ast) {
                    stack.pop();
                    continue;
                } else if (stack.peek() == -ast) {
                    stack.pop();
                }
                destroyed = true;
                break;
            }
            if (!destroyed) {
                stack.push(ast);
            }
        }
        int[] result = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; --i) {
            result[i] = stack.pop();
        }
        return result;
    }
}
      

var asteroidCollision = function(asteroids) {
    let stack = [];
    for (let ast of asteroids) {
        let destroyed = false;
        while (stack.length > 0 && ast < 0 && stack[stack.length - 1] > 0) {
            if (stack[stack.length - 1] < -ast) {
                stack.pop();
                continue;
            } else if (stack[stack.length - 1] === -ast) {
                stack.pop();
            }
            destroyed = true;
            break;
        }
        if (!destroyed) {
            stack.push(ast);
        }
    }
    return stack;
};
      

Problem Description

You are given an array asteroids of integers, where each element represents an asteroid in a row. The absolute value of each integer is the size of the asteroid, and the sign determines its direction: positive means moving to the right, negative means moving to the left.

When two asteroids collide, the smaller one explodes. If both are the same size, both explode. Two asteroids moving in the same direction never meet. Return an array of the asteroids that remain after all collisions.

• Each asteroid moves at the same speed.
• There is always one valid answer; do not reuse or alter the original asteroid values.
• Constraints: 1 <= asteroids.length <= 10^4, -1000 <= asteroids[i] <= 1000, asteroids[i] != 0

Thought Process

At first, it seems like we could check every possible pair of asteroids for collisions, but this would be slow and inefficient, especially for large inputs. Instead, we need to find a way to efficiently simulate the process of asteroids moving and colliding, while only considering those that could actually meet.

Since only asteroids moving towards each other (one right, one left) can collide, we can process the asteroids from left to right, keeping track of those that have not yet been destroyed. A stack is a natural fit for this, as it allows us to compare new asteroids with the most recent survivors, and to "undo" or remove asteroids that are destroyed in collisions.

The main conceptual leap here is realizing that for each left-moving asteroid, we only need to check the right-moving asteroids that are still "active" and have not yet collided. This avoids unnecessary comparisons and helps us build an efficient solution.

Solution Approach

• Use a stack: Iterate through the asteroids array, using a stack to keep track of asteroids that are still active and have not been destroyed.
• Collision detection: When a new asteroid is moving left (negative) and the top of the stack is moving right (positive), a collision may occur. Compare their sizes:
  • If the right-moving asteroid is smaller, it explodes (pop from stack) and check again.
  • If both are the same size, both explode (pop from stack and do not push the new one).
  • If the right-moving asteroid is larger, the new one explodes (do not push it).
• No collision: If the new asteroid is moving right, or the stack is empty, or the top of the stack is moving left, simply push the new asteroid onto the stack.
• Repeat: Continue this process for all asteroids.
• Result: The stack will contain all surviving asteroids in order.

This approach is efficient because each asteroid is pushed and popped at most once, leading to linear time complexity.

Example Walkthrough

Let's use the input [5, 10, -5] as an example:

1. Start with an empty stack.
2. Process 5: It's moving right, so push onto the stack. Stack: [5]
3. Process 10: Also moving right, push onto the stack. Stack: [5, 10]
4. Process -5: Moving left, check top of stack (10, right-moving). Since 10 > 5, -5 explodes. Stack remains [5, 10].
5. No more asteroids; return [5, 10].

Now, try [8, -8]:

1. Stack: []
2. Process 8: push. Stack: [8]
3. Process -8: 8 and -8 are equal size and opposite direction, both explode. Stack: []
4. Return []

Time and Space Complexity

• Brute-force approach: Comparing every pair could be O(n^2), which is inefficient for large inputs.
• Optimized stack approach: Each asteroid is pushed and popped at most once, so the time complexity is O(n), where n is the number of asteroids.
• Space complexity: In the worst case (no collisions), all asteroids are stored in the stack, so space is O(n).

The optimized stack approach is both time and space efficient for this problem.

Summary

The key insight for the Asteroid Collision problem is to use a stack to efficiently simulate the process of collisions, only comparing asteroids that could actually meet. This avoids redundant checks and ensures that each asteroid is processed in constant time. The solution is elegant because it leverages the properties of stacks and the problem's constraints to achieve optimal performance and clarity.