Pseudo-Code:

text
while collision_exists:
    find index i where asteroids[i] is right(+) and asteroids[i+1] is left(-)
    if abs(asteroids[i]) > abs(asteroids[i+1]):
        remove asteroids[i+1]
    else if abs(asteroids[i]) < abs(asteroids[i+1]):
        remove asteroids[i]
    else:
        remove both

Why this fails: The time complexity of this approach is O(N²). Removing elements from an array (shifting subsequent elements) takes O(N) time. In the worst-case scenario (e.g., many right-moving asteroids followed by many left-moving asteroids), we might perform O(N) removals. Given the constraint N <= 10^4, an O(N²) solution performs roughly $10^8$ operations, which may lead to a Time Limit Exceeded (TLE) error or perform poorly in an interview setting.

Core Insight for Asteroid Collision

The key intuition is that we can process the asteroids from left to right and maintain a "stable" state of survivors in a stack.

The stack represents the asteroids that have survived all collisions so far and are currently moving safely.

1. Safety Condition: A collision only happens when a Left-Moving (-) asteroid encounters a Right-Moving (+) asteroid that is already in the stack.
2. No Collision:
   • If the stack is empty.
   • If the current asteroid is moving Right (+).
   • If the stack top is moving Left (-). (Two left-moving asteroids never collide; they just follow each other).

When we encounter a Left-Moving asteroid, we check it against the top of the stack (the rightmost survivor). We repeatedly "pop" from the stack as long as the incoming left-asteroid destroys the stack top. If the stack top destroys the incoming asteroid, we stop.

Visual Description: Imagine the stack as the "safe zone" to the left of our current position.

• We push 5 (Right). Stack: [5].
• We push 10 (Right). Stack: [5, 10].
• We encounter -5 (Left). It clashes with 10. Since 10 > |-5|, the -5 explodes. The stack remains [5, 10].
• If we encountered -15 instead: It clashes with 10. 10 explodes (pop). Then it clashes with 5. 5 explodes (pop). The stack becomes empty, and -15 survives (push).

Execution Flow

Consider Input: [10, 2, -5]

1. Initialize: Stack = []
2. Process 10:
   • Positive. No collision check needed.
   • Push 10.
   • Stack: [10]
3. Process 2:
   • Positive. No collision check needed.
   • Push 2.
   • Stack: [10, 2]
4. Process -5:
   • Negative. Stack top (2) is Positive. Collision!
   • Compare |-5| vs 2. 5 > 2.
   • Stack top 2 explodes (Pop).
   • Stack: [10]. Current -5 is still alive.
   • Loop continues.
   • Stack top (10) is Positive. Collision!
   • Compare |-5| vs 10. 5 < 10.
   • Current -5 explodes.
   • Stop processing -5.
   • Stack: [10]
5. Result: [10]

Proof of Correctness

The algorithm maintains an invariant: the stack always contains a sequence of asteroids that will never collide with each other. This is guaranteed because:

1. We only push positive asteroids freely.
2. We only push negative asteroids if the stack is empty or the top is also negative (safe state).
3. If a negative asteroid encounters positive ones, we simulate the physics exactly as described until stability is reached. Since we process every asteroid exactly once and resolve all its potential collisions before moving to the next, the final stack state represents the correct simulation outcome.

Reference Implementation

C++ Solution for LeetCode 735

cpp
class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> st; // Using vector as a stack for easy result return

        for (int asteroid : asteroids) {
            bool exploded = false;

            // Collision loop: while current is moving left (-) and top is moving right (+)
            while (!st.empty() && asteroid < 0 && st.back() > 0) {
                if (abs(asteroid) > st.back()) {
                    st.pop_back(); // Top explodes, current continues
                    continue;
                } else if (abs(asteroid) == st.back()) {
                    st.pop_back(); // Both explode
                    exploded = true;
                    break;
                } else {
                    exploded = true; // Current explodes
                    break;
                }
            }

            if (!exploded) {
                st.push_back(asteroid);
            }
        }

        return st;
    }
};

Java Solution for LeetCode 735

java
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();

        for (int asteroid : asteroids) {
            boolean exploded = false;

            // Handle collision
            while (!stack.isEmpty() && asteroid < 0 && stack.peek() > 0) {
                if (Math.abs(asteroid) > stack.peek()) {
                    stack.pop(); // Top explodes
                    continue;
                } else if (Math.abs(asteroid) == stack.peek()) {
                    stack.pop(); // Both explode
                    exploded = true;
                    break;
                } else {
                    exploded = true; // Current explodes
                    break;
                }
            }

            if (!exploded) {
                stack.push(asteroid);
            }
        }

        // Convert stack to array
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        return result;
    }
}

Python Solution for LeetCode 735

python
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []

        for asteroid in asteroids:
            # Flag to track if the current asteroid survives
            exploded = False
            
            # Collision happens if stack has right-moving (+) and current is left-moving (-)
            while stack and asteroid < 0 and stack[-1] > 0:
                if abs(asteroid) > stack[-1]:
                    stack.pop() # Top explodes, check next
                    continue
                elif abs(asteroid) == stack[-1]:
                    stack.pop() # Both explode
                    exploded = True
                    break
                else:
                    exploded = True # Current explodes
                    break
            
            if not exploded:
                stack.append(asteroid)
        
        return stack

• Mistake: Assuming any negative number collides with the stack top.
• Why: A collision only occurs if the stack top is Positive (Right) and the current is Negative (Left). Two negative asteroids simply move left together without touching.
• Consequence: Incorrect output where non-colliding asteroids are removed.