Asteroid Collisions | Stack and Queue

1. Problem Statement & Fundamental Rules

The Asteroid Collision problem requires us to simulate the final state of an array of moving asteroids after all possible collisions have resolved.

We are given an array of integers representing asteroids:

• Absolute Value (|element|): Represents the size or mass of the asteroid.
• Sign (+ or -): Represents the direction of movement:
  • Positive numbers (> 0): Moving continuously toward the right.
  • Negative numbers (< 0): Moving continuously toward the left.

Core Collision Mechanics

1. Directional Requirement for Collision: Collisions only occur when a right-moving asteroid is positioned to the left of a left-moving asteroid, and they are heading toward each other (i.e., a positive value followed by a negative value: ... (+A) ... (-B) ...).
   • If a negative asteroid precedes a positive asteroid (... (-A) ... (+B) ...), they travel away from each other and never collide.
   • Asteroids moving in the exact same direction (all positive or all negative sequentially) never collide.
2. Mass Destruction (Unequal Sizes): When two moving asteroids collide, the one with the smaller absolute value (size) is completely destroyed. The larger asteroid survives intact and continues its motion.
3. Mutual Annihilation (Equal Sizes): If two colliding asteroids have the exact same absolute value, both of them are destroyed simultaneously.

2. Core Mental Model & Data Structure Selection

Real-Life Analogy

Imagine a single-lane hallway where people are walking. People on the left side are walking forward (right), and someone entering from the far right starts walking backward (left). When the leftward walker bumps into people walking forward, they engage in conflicts dynamically from the most recent person encountered backwards.

Why a Stack (or List) is Needed

When a negative asteroid enters from the right and moves left, it collides with the most recently seen right-moving asteroids first.

• If that right-moving asteroid is destroyed, our negative asteroid moves on to collide with the previous right-moving asteroid.
• This Last-In, First-Out (LIFO) behavior matches the Stack data structure.
• Practical Implementation Detail: Instead of using a strict Stack (which would require reversing elements at the end because a stack pops in reverse order), we can use a List/Vector that behaves like a stack. This allows us to inspect the back element and return the final collection in the correct left-to-right order without extra reversal steps.

3. Step-by-Step Simulation & Scenarios

Let's trace how elements enter and trigger collisions using a concrete array: [4, 7, 1, 1, 2, -3].

Step-by-Step Walkthrough:

1. Process 4: Stack is empty. 4 is positive. Push to stack. ([4])
2. Process 7: Positive. Push to stack. ([4, 7])
3. Process 1, 1, 2: All positive. Push sequentially. ([4, 7, 1, 1, 2])
4. Process -3: Negative! Collision check triggered against the top of the stack (2):
   • 2 is smaller than absolute value of -3 (2 < 3).
   • 2 is destroyed (pop from stack). Stack top is now 1.
   • Next collision: -3 vs top element 1. 1 < 3, so 1 is destroyed (pop).
   • Next collision: -3 vs top element 1. 1 < 3, so 1 is destroyed (pop).
   • Next collision: -3 vs top element 7. Here, 7 > 3. The positive asteroid 7 survives, and the incoming negative asteroid -3 is destroyed and not pushed into the stack.
5. Final Result for this segment: [4, 7]

4. Critical Edge Cases

Handling edge cases correctly prevents runtime errors and infinite loops:

1. Identical Magnitude Collision: When a right-moving asteroid and left-moving asteroid collide with identical sizes (+7 and -7), both are destroyed. We pop the stack element and discard the incoming negative asteroid.
2. Stack Becomes Empty: If a negative asteroid successfully destroys all preceding positive asteroids until the stack is completely empty, the negative asteroid has nothing left to collide with. At this point, it must be pushed into the stack.
3. Consecutive Negative Asteroids: If the stack top is already a negative asteroid (< 0) and the incoming asteroid is also negative (< 0), they are moving in the same direction and cannot collide. The incoming negative asteroid is safely pushed into the stack.

5. Algorithmic Approach & Pseudo Code

We iterate through the array once. For every element:

• If it's positive, push it to our list (St).
• If it's negative, resolve all potential collisions using a while loop against the back of the list as long as the stack is non-empty, the top element is positive, and the top element is smaller than the absolute value of our current negative asteroid.

function asteroidCollision(asteroids):
    St = []  # List acting as a stack
    
    for val in asteroids:
        # Case 1: Handle incoming negative asteroid collisions
        while St is not empty and St.back() > 0 and St.back() < abs(val):
            St.pop_back()  # Top element gets destroyed
            
        # Case 2: Handle identical magnitude destruction
        if St is not empty and St.back() > 0 and St.back() == abs(val):
            St.pop_back()  # Destroy top element
            # Current negative asteroid is also destroyed (do not push)
            
        # Case 3: Safe to push current asteroid
        else:
            # Push if: 
            # 1. Stack is empty, OR
            # 2. Current asteroid is positive, OR
            # 3. Stack top is already negative (moving same direction)
            if val > 0 or St is empty or St.back() < 0:
                St.push_back(val)
                
    return St

6. Language-Specific Implementation Reference (Java Code Pattern)

For practical coding in interviews, implementing this with a Stack<Integer> or LinkedList in Java follows the exact same logic:

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> st = new Stack<>();
        
        for (int i = 0; i < asteroids.length; i++) {
            int val = asteroids[i];
            
            // Resolve collisions for negative asteroids against right-moving stack tops
            while (!st.isEmpty() && st.peek() > 0 && st.peek() < Math.abs(val)) {
                st.pop();
            }
            
            // Handle equal size annihilation
            if (!st.isEmpty() && st.peek() > 0 && st.peek() == Math.abs(val)) {
                st.pop(); // destroy both
            } 
            else {
                // Push if positive, or if stack is empty, or if stack top is moving left (<0)
                if (val > 0 || st.isEmpty() || st.peek() < 0) {
                    st.push(val);
                }
            }
        }
        
        // Convert stack to array
        int[] result = new int[st.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = st.pop();
        }
        return result;
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Problem Nature: Simulating physical collisions based on directional vectors (+ right, - negative).
• Collision Condition: Only happens when a positive asteroid appears before a negative asteroid (+ ... -).
• Data Structure Choice: A Stack (or List acting as a LIFO structure) is optimal because collisions resolve against the most recently encountered preceding elements.
• Size Comparison: Smaller absolute values are destroyed; equal values result in mutual annihilation.
• Edge Case Safety: Always account for empty stacks and consecutive negative elements moving in the same leftward direction.
• Optimal Efficiency: Achieves linear $\mathcal{O}(N)$ time complexity because each element enters and leaves the stack a maximum of one time.