Asteroid Collision

LeetCode 735: Asteroid Collision Solution & Explanation

Problem Overview

TL;DR: Use a stack to maintain the state of asteroids moving right, resolving collisions immediately when a left-moving asteroid is encountered by popping smaller right-moving asteroids.

The Asteroid Collision problem asks us to simulate the aftermath of a series of asteroid collisions in a single row. We are given an array where the absolute value represents size and the sign represents direction (positive for right, negative for left). When two asteroids collide, the smaller one explodes. If they are the same size, both explode. We need to return the state of the asteroids after all collisions are resolved.

This is a popular interview question, and the optimal LeetCode 735 Solution requires handling sequential dependencies efficiently.

Brute Force Approach for Asteroid Collision

The naive approach attempts to simulate the collisions by repeatedly scanning the array for adjacent collision pairs. A collision pair is defined as a positive number immediately followed by a negative number (e.g., [..., 10, -5, ...]).

1. Iterate through the array to find the first index i where asteroids[i] > 0 and asteroids[i+1] < 0.
2. Resolve the collision based on their sizes.
3. Remove the destroyed asteroid(s) from the array.
4. Repeat the scan from the beginning (or slightly before the collision index) until no such pairs exist.

Pseudo-Code:

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.

Algorithm Strategy: Stack Patterns

1. Initialize an empty Stack to store the surviving asteroids.
2. Iterate through the asteroids array one by one.
3. For each asteroid:
   • Check if it interacts with the top of the stack. An interaction occurs only if the current asteroid is negative (< 0) and the stack top is positive (> 0).
   • While there is an interaction:
     • Compare the size of the current asteroid (abs(current)) with the stack top (top).
     • Case A (Top < Current): The stack top explodes. Pop the stack. Continue the loop to compare the current asteroid with the new top.
     • Case B (Top == Current): Both explode. Pop the stack. Mark the current asteroid as destroyed and break the loop (do not push it).
     • Case C (Top > Current): The current asteroid explodes. Mark it as destroyed and break the loop.
   • If the current asteroid survived the collision checks (or never collided), push it onto the stack.
4. Convert the stack content to an array and return it.

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.

Pattern Reuse Notes

The Stack - Simulation / Backtracking Helper pattern is versatile. It applies when element interactions depend on immediate history.

• LeetCode 71: Simplify Path: Uses a stack to resolve directory path components (e.g., .. pops the previous directory).
• LeetCode 394: Decode String: Uses a stack to handle nested encoding brackets, simulating the expansion process from inside out.

Reference Implementation

C++ Solution for LeetCode 735

1class Solution {
2public:
3    vector<int> asteroidCollision(vector<int>& asteroids) {
4        vector<int> st; // Using vector as a stack for easy result return
5
6        for (int asteroid : asteroids) {
7            bool exploded = false;
8
9            // Collision loop: while current is moving left (-) and top is moving right (+)
10            while (!st.empty() && asteroid < 0 && st.back() > 0) {
11                if (abs(asteroid) > st.back()) {
12                    st.pop_back(); // Top explodes, current continues
13                    continue;
14                } else if (abs(asteroid) == st.back()) {
15                    st.pop_back(); // Both explode
16                    exploded = true;
17                    break;
18                } else {
19                    exploded = true; // Current explodes
20                    break;
21                }
22            }
23
24            if (!exploded) {
25                st.push_back(asteroid);
26            }
27        }
28
29        return st;
30    }
31};

Java Solution for LeetCode 735

1class Solution {
2    public int[] asteroidCollision(int[] asteroids) {
3        Stack<Integer> stack = new Stack<>();
4
5        for (int asteroid : asteroids) {
6            boolean exploded = false;
7
8            // Handle collision
9            while (!stack.isEmpty() && asteroid < 0 && stack.peek() > 0) {
10                if (Math.abs(asteroid) > stack.peek()) {
11                    stack.pop(); // Top explodes
12                    continue;
13                } else if (Math.abs(asteroid) == stack.peek()) {
14                    stack.pop(); // Both explode
15                    exploded = true;
16                    break;
17                } else {
18                    exploded = true; // Current explodes
19                    break;
20                }
21            }
22
23            if (!exploded) {
24                stack.push(asteroid);
25            }
26        }
27
28        // Convert stack to array
29        int[] result = new int[stack.size()];
30        for (int i = result.length - 1; i >= 0; i--) {
31            result[i] = stack.pop();
32        }
33        return result;
34    }
35}

Python Solution for LeetCode 735

1class Solution:
2    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
3        stack = []
4
5        for asteroid in asteroids:
6            # Flag to track if the current asteroid survives
7            exploded = False
8            
9            # Collision happens if stack has right-moving (+) and current is left-moving (-)
10            while stack and asteroid < 0 and stack[-1] > 0:
11                if abs(asteroid) > stack[-1]:
12                    stack.pop() # Top explodes, check next
13                    continue
14                elif abs(asteroid) == stack[-1]:
15                    stack.pop() # Both explode
16                    exploded = True
17                    break
18                else:
19                    exploded = True # Current explodes
20                    break
21            
22            if not exploded:
23                stack.append(asteroid)
24        
25        return stack