110. Asteroid Collision

🔗 LeetCode Problem: 735. Asteroid Collision
📊 Difficulty: Medium
🏷️ Topics: Stack, Array, Simulation

Problem Statement

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]

Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []

Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]

Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints: - 2 <= asteroids.length <= 10^4 - -1000 <= asteroids[i] <= 1000 - asteroids[i] != 0

🌟 ELI5: The Simple Idea!

Think of asteroids moving towards each other:

Positive = Moving right →
Negative = Moving left  ←

[5, 10, -5]
 →  →   ←

Only 10 and -5 collide:
  10 > 5, so 10 survives

Result: [5, 10]

Collision Rules:

1. → → : Never collide (same direction)
2. ← ← : Never collide (same direction)
3. ← → : Never collide (moving apart)
4. → ← : COLLISION! (moving towards each other)

When collision happens:
  - Bigger survives
  - Equal? Both explode
  - Winner might collide with next asteroid!

🎨 Visual Understanding

Example 1: Simple Collision

Input: [5, 10, -5]

Step by step:

Initial:  5→  10→  ←5
          ────────────→ direction

Stack: []

Process 5:
  Stack: [5]  (no collision, moving right)

Process 10:
  Stack: [5, 10]  (no collision, both moving right)

Process -5:
  Moving left, meets 10 moving right!
  Collision: 10 vs 5
  10 wins (10 > 5)
  Stack: [5, 10]

Result: [5, 10] ✓

Example 2: Equal Collision

Input: [8, -8]

Initial:  8→  ←8

Process 8:
  Stack: [8]

Process -8:
  Collision: 8 vs 8
  Equal! Both explode
  Stack: []

Result: [] ✓

Example 3: Chain Collision

Input: [10, 2, -5]

Initial:  10→  2→  ←5

Process 10:
  Stack: [10]

Process 2:
  Stack: [10, 2]

Process -5:
  Collision 1: 2 vs 5
    5 wins (5 > 2)
    Pop 2, -5 continues
    Stack: [10]

  Collision 2: 10 vs 5
    10 wins (10 > 5)
    Stack: [10]

Result: [10] ✓

🎯 Approach: Stack Simulation ⭐⭐⭐

The Standard Solution

Algorithm:

Use stack to track surviving asteroids

For each asteroid:
  If moving right (positive):
    Push to stack (might collide later)

  If moving left (negative):
    While collision possible:
      Compare with stack top
      - If smaller: break (current explodes)
      - If equal: pop and break (both explode)
      - If larger: pop top (top explodes, continue)

    If survived collisions: push to stack

Implementation

/**
 * Stack-based collision simulation
 * Time: O(n), Space: O(n)
 */
public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();

    for (int asteroid : asteroids) {
        if (asteroid > 0) {
            // Moving right, no immediate collision
            stack.push(asteroid);
        } else {
            // Moving left, check for collisions
            boolean survived = true;

            while (!stack.isEmpty() && stack.peek() > 0) {
                int top = stack.peek();

                if (top < Math.abs(asteroid)) {
                    // Top explodes, current continues
                    stack.pop();
                } else if (top == Math.abs(asteroid)) {
                    // Both explode
                    stack.pop();
                    survived = false;
                    break;
                } else {
                    // Current explodes
                    survived = false;
                    break;
                }
            }

            // If survived all collisions, add to stack
            if (survived) {
                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;
}

⏰ Time: O(n) - Each asteroid processed at most twice
💾 Space: O(n) - Stack storage

Cleaner Version

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

    for (int ast : asteroids) {
        boolean alive = true;

        // Check collision: current moving left, stack top moving right
        while (alive && ast < 0 && !stack.isEmpty() && stack.peek() > 0) {
            if (stack.peek() < -ast) {
                stack.pop();  // Top explodes
                continue;
            } else if (stack.peek() == -ast) {
                stack.pop();  // Both explode
            }
            alive = false;  // Current explodes or both explode
        }

        if (alive) {
            stack.push(ast);
        }
    }

    // Convert to array
    return stack.stream().mapToInt(i -> i).toArray();
}

🔍 Super Detailed Dry Run

Example: asteroids = [10, 2, -5]

Goal: Simulate asteroid collisions

═══════════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════════

stack = []
asteroids = [10, 2, -5]

═══════════════════════════════════════════════════════════════
Iteration 1: asteroid = 10
═══════════════════════════════════════════════════════════════

Check: asteroid > 0? Yes (10 > 0)

Action: Moving right, push to stack
  stack.push(10)

State:
  stack: [10]

Visualization:
  10→

No collision possible yet

═══════════════════════════════════════════════════════════════
Iteration 2: asteroid = 2
═══════════════════════════════════════════════════════════════

Check: asteroid > 0? Yes (2 > 0)

Action: Moving right, push to stack
  stack.push(2)

State:
  stack: [10, 2]

Visualization:
  10→ 2→

Both moving right, no collision

═══════════════════════════════════════════════════════════════
Iteration 3: asteroid = -5
═══════════════════════════════════════════════════════════════

Check: asteroid > 0? No (-5 < 0)

Action: Moving left, check for collisions
  survived = true

Visualization:
  10→ 2→ ←5
      ⚡ Collision will happen!

Collision Loop:

  ───────────────────────────────────────────────────────────
  Collision Check 1:
  ───────────────────────────────────────────────────────────

  While condition:
    - !stack.isEmpty()? Yes
    - stack.peek() > 0? Yes (2 > 0)
    - Continue to collision logic

  top = stack.peek() = 2
  current = -5 (size = 5)

  Compare: top < |asteroid|?
          2 < 5? Yes

  Action: Top explodes
    stack.pop()  // Remove 2
    Continue loop (current -5 still alive)

  State:
    stack: [10]
    survived: true

  Explanation:
    2→ vs ←5: 5 wins, 2 explodes

  ───────────────────────────────────────────────────────────
  Collision Check 2:
  ───────────────────────────────────────────────────────────

  While condition:
    - !stack.isEmpty()? Yes
    - stack.peek() > 0? Yes (10 > 0)
    - Continue to collision logic

  top = stack.peek() = 10
  current = -5 (size = 5)

  Compare: top < |asteroid|?
          10 < 5? No

  Compare: top == |asteroid|?
          10 == 5? No

  Else: top > |asteroid|
        10 > 5? Yes

  Action: Current explodes
    survived = false
    break

  State:
    stack: [10]
    survived: false

  Explanation:
    10→ vs ←5: 10 wins, 5 explodes

  ───────────────────────────────────────────────────────────
  End of Collision Loop
  ───────────────────────────────────────────────────────────

Check: survived? No (false)

Action: Do not push -5 to stack

State:
  stack: [10]

═══════════════════════════════════════════════════════════════
Final Result
═══════════════════════════════════════════════════════════════

Convert stack to array:
  result = [10]

Return: [10] ✓

Summary:
  10 survives
  2 explodes (lost to -5)
  -5 explodes (lost to 10)

Example 2: asteroids = [8, -8]

Process 8:
  8 > 0 → Push
  stack: [8]

Process -8:
  -8 < 0 → Check collisions

  Collision:
    top = 8
    current = -8 (size = 8)

    Compare: 8 == 8? Yes
    Action: Both explode
      stack.pop()  // Remove 8
      survived = false

  stack: []

Result: [] ✓

Example 3: asteroids = [5, 10, -5]

Process 5:
  stack: [5]

Process 10:
  stack: [5, 10]

Process -5:
  Collision with 10:
    10 > 5 → 10 wins
    -5 explodes

  stack: [5, 10]

Result: [5, 10] ✓

🎯 Why This Solution Works

The Key Insight

Why stack for asteroid collision?

1. Collision only happens: → ←
   Right-moving meets left-moving

2. Left-moving asteroid collides with
   MOST RECENT right-moving asteroid

   This is exactly what stack.peek() gives us!

3. If left-moving wins:
   - Pop loser
   - Check next asteroid (continue loop)
   - Might cause chain reactions!

4. Stack naturally stores survivors
   in order from left to right

Collision Conditions

When does collision happen?

Current asteroid (new):  negative (←)
Stack top (previous):    positive (→)

          prev  current
Example:   10→   ←5

This is the ONLY collision scenario!

NO collision cases:
  → → : Both right (never meet)
  ← ← : Both left (never meet)
  ← → : Moving apart (never meet)

Chain Reaction Handling

Why while loop for collisions?

Example: [10, 2, 1, -5]

Process -5:
  Collision 1: 1 vs 5 → 5 wins, pop 1
  Collision 2: 2 vs 5 → 5 wins, pop 2
  Collision 3: 10 vs 5 → 10 wins, -5 explodes

One left-moving asteroid can destroy
MULTIPLE right-moving asteroids!

While loop continues until:
  - Current explodes, OR
  - No more collisions possible

⚠️ Common Mistakes

Mistake 1: Not using absolute value for comparison

// ❌ WRONG - Comparing negative with positive!
if (stack.peek() < asteroid) {
    // -5 < 10 is always true, wrong logic!
}

// ✓ CORRECT - Compare sizes
if (stack.peek() < Math.abs(asteroid)) {
    // 10 < 5? Correct comparison
}

Or:
if (stack.peek() < -asteroid) {
    // If asteroid = -5, then -asteroid = 5
}

Mistake 2: Not checking stack.peek() > 0

// ❌ WRONG - Collision with left-moving asteroid!
while (!stack.isEmpty() && asteroid < 0) {
    // What if stack.peek() is also negative?
    // ← ← : No collision!
}

// ✓ CORRECT - Only collide with right-moving
while (!stack.isEmpty() && stack.peek() > 0 && asteroid < 0) {
    // Now guaranteed: → ←
}

Mistake 3: Breaking on first collision

// ❌ WRONG - Doesn't handle chain reactions!
if (asteroid < 0 && !stack.isEmpty() && stack.peek() > 0) {
    if (stack.peek() < Math.abs(asteroid)) {
        stack.pop();
    }
}
// Only checks one collision!

// ✓ CORRECT - While loop for multiple collisions
while (!stack.isEmpty() && stack.peek() > 0 && asteroid < 0) {
    // Can pop multiple asteroids
}

Mistake 4: Not tracking survived flag

// ❌ WRONG - Always pushes asteroid!
while (/* collision conditions */) {
    if (stack.peek() == Math.abs(asteroid)) {
        stack.pop();
        break;
    }
}
stack.push(asteroid);  // Pushes even if exploded!

// ✓ CORRECT - Track if survived
boolean survived = true;
while (/* collision conditions */) {
    if (stack.peek() == Math.abs(asteroid)) {
        stack.pop();
        survived = false;
        break;
    }
}
if (survived) {
    stack.push(asteroid);
}

Mistake 5: Wrong result array conversion

// ❌ WRONG - Reversed order!
int[] result = new int[stack.size()];
for (int i = 0; i < result.length; i++) {
    result[i] = stack.pop();  // LIFO gives reversed!
}

// ✓ CORRECT - Pop in reverse
int[] result = new int[stack.size()];
for (int i = result.length - 1; i >= 0; i--) {
    result[i] = stack.pop();
}

// Or use stream
return stack.stream().mapToInt(i -> i).toArray();

🎯 Pattern Recognition

Problem Type: Collision Simulation
Core Pattern: Stack Pattern 7 - Collision/Cancellation

When to Apply:
✓ Elements can cancel each other
✓ Direction-based interactions
✓ Chain reactions possible
✓ Process elements sequentially

Recognition Keywords:
- "collision"
- "moving in directions"
- "cancel out"
- "explode"
- "positive/negative"
- "after all interactions"

Similar Problems:
- Remove All Adjacent Duplicates (LC 1047)
- Remove K Adjacent Duplicates (LC 1209)
- Valid Parentheses (LC 20) - Matching cancels
- Backspace String Compare (LC 844)

Key Components:
┌────────────────────────────────────────────┐
│ Stack: Track surviving elements           │
│ Right (+): Always push initially          │
│ Left (-): Check collisions with stack top │
│ While loop: Handle chain reactions        │
│ Compare: Use absolute value               │
│ Survived flag: Track if element lives     │
│ Time: O(n), Space: O(n)                   │
└────────────────────────────────────────────┘

🧠 Interview Strategy

Step 1: "This is a collision simulation problem"
Step 2: "I'll use stack to track survivors"
Step 3: "Check collisions for left-moving asteroids"

Key Points to Mention:
- Stack stores surviving asteroids left to right
- Right-moving (+): push immediately
- Left-moving (-): check collisions with stack top
- Collision only between → and ←
- While loop handles chain reactions
- Compare absolute values for sizes

Walk Through Example:
"For [10, 2, -5]:
 10: Push (right) → [10]
 2: Push (right) → [10, 2]
 -5: Moving left, collide with 2
     2 < 5, pop 2 → [10]
     Collide with 10
     10 > 5, -5 explodes → [10]
 Result: [10]"

Why Stack:
"Stack gives O(1) access to most recent
 right-moving asteroid. Left-moving collides
 with most recent first. Stack order matches
 spatial order of asteroids."

Complexity:
"Time O(n) - each asteroid pushed/popped once.
 Space O(n) - stack stores survivors."

Edge Cases to Mention:
✓ All moving right: no collisions
✓ All moving left: no collisions
✓ Equal sizes: both explode
✓ Chain reactions: one destroys multiple

📝 Quick Revision Notes

🎯 Core Concept:

Asteroid Collision: Use stack to track survivors. Right-moving (+) → push. Left-moving (-) → while loop to check collisions with stack top (if top > 0). Compare sizes with Math.abs(). Pop loser, track survived flag. Chain reactions handled by while.

⚡ Quick Implementation:

import java.util.Arrays;
import java.util.Stack;

class Solution {
  public int[] asteroidCollision(int[] asteroids) {
    // Main key logic. Only case 4 to be considered.
    // +ve means -> and -ve means <- (direction)
    // case 1: -> (+ve), -> (+ve) : Never collide (same direction)
    // case 2: <- (-ve), <- (-ve) : Never collide (same direction)
    // case 3: <- (-ve), -> (+ve) : Never collide (moving apart)
    // case 4: -> (+ve) <-  (-ve) : COLLISION! (moving towards each other)
    Stack<Integer> stack = new Stack<>();
    for(int asteroid : asteroids) {
      if(asteroid > 0) {
        // simply push to stak as there is no harm. Check above (Never collide)
        stack.push(asteroid);

        continue;
      }

      boolean survived = true; // true means push the incoming one onto the stack.
      // We have to check for collision as per scenario 4 only.
      while (!stack.isEmpty() && stack.peek() > 0) {
        int top = stack.peek();

        if(top > Math.abs(asteroid)) {
          survived = false; // incoming did not get survive. BREAK for next.
          break;
        } else if (top == Math.abs(asteroid)) {
          survived = false; // incoming did not get survive
          stack.pop(); // also the current one on the stack.
          break;
        } else {
          stack.pop();
        }
      }

      if(survived) {
        stack.push(asteroid);
      }
    }

    int size = stack.size();    
    if(size == 0) {
      return new int[]{};
    }

    int[] res = new int[size];
    for(int i = size - 1; i >= 0; i--) {
      res[i] = stack.pop();
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(Arrays.toString(s.asteroidCollision(new int[] {5,10,-5})));
    System.out.println(Arrays.toString(s.asteroidCollision(new int[] {8,-8})));
    System.out.println(Arrays.toString(s.asteroidCollision(new int[] {10,2,-5})));
    System.out.println(Arrays.toString(s.asteroidCollision(new int[] {3,5,-6,2,-1,4})));
    System.out.println(Arrays.toString(s.asteroidCollision(new int[] {-2,-2,1,-2})));
  }
}

🔑 Key Insights:

Pattern: Stack Pattern 7 (Collision/Cancellation)
Collision: Only → ← (right meets left)
While loop: Handle chain reactions
Absolute value: Compare sizes correctly
Survived flag: Track if asteroid lives
Time: O(n), Space: O(n) ✓

🎪 Memory Aid:

"Right push, left collide, while for chain!"
"Stack tracks survivors, compare absolute!" ✨

⚠️ Critical Conditions:

Three checks for collision:

1. alive && ast < 0
   Current is left-moving

2. !stack.isEmpty()
   There's something to collide with

3. stack.peek() > 0
   It's right-moving (collision possible)

ALL THREE needed for collision!

🧪 Edge Cases

Case 1: All moving right

Input: [1, 2, 3]
Output: [1, 2, 3]
No collisions

Case 2: All moving left

Input: [-3, -2, -1]
Output: [-3, -2, -1]
No collisions

Case 3: Moving apart

Input: [-1, 1]
Output: [-1, 1]
← → no collision

Case 4: Equal collision

Input: [5, -5]
Output: []
Both explode

Case 5: Chain reaction

Input: [10, 2, 1, -5]
Output: [10]
-5 destroys 1 and 2, loses to 10

Case 6: Left wins all

Input: [1, 2, 3, -10]
Output: [-10]
-10 destroys all right-moving

All handled correctly! ✓

🎓 Complexity Analysis

Time Complexity: O(n)

Each asteroid:
  - Pushed to stack: once
  - Popped from stack: at most once

Total operations: ≤ 2n

Example: [1, 2, 3, -10]
  Push 1, 2, 3: 3 pushes
  Process -10: pop 3, 2, 1: 3 pops
  Total: 6 operations for 4 asteroids

O(n) ✓

Space Complexity: O(n)

Stack space:
  Worst case: all asteroids survive
  Example: [1, 2, 3, 4, 5]
  Stack: [1, 2, 3, 4, 5]

Result array: O(n)

Total: O(n) ✓

🔄 Variations & Extensions

Extension 1: Return Explosion Count

public int countExplosions(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    int explosions = 0;

    for (int ast : asteroids) {
        boolean alive = true;

        while (alive && ast < 0 && !stack.isEmpty() && stack.peek() > 0) {
            if (stack.peek() < -ast) {
                stack.pop();
                explosions++;  // Top exploded
            } else if (stack.peek() == -ast) {
                stack.pop();
                explosions += 2;  // Both exploded
                alive = false;
            } else {
                explosions++;  // Current exploded
                alive = false;
            }
        }

        if (alive) {
            stack.push(ast);
        }
    }

    return explosions;
}

Extension 2: Track Collision Positions

public List<Integer> collisionPositions(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    List<Integer> positions = new ArrayList<>();

    for (int i = 0; i < asteroids.length; i++) {
        boolean alive = true;

        while (alive && asteroids[i] < 0 && !stack.isEmpty() && asteroids[stack.peek()] > 0) {
            int topIdx = stack.peek();

            if (asteroids[topIdx] < -asteroids[i]) {
                stack.pop();
                positions.add(topIdx);
            } else if (asteroids[topIdx] == -asteroids[i]) {
                stack.pop();
                positions.add(topIdx);
                positions.add(i);
                alive = false;
            } else {
                positions.add(i);
                alive = false;
            }
        }

        if (alive) {
            stack.push(i);
        }
    }

    return positions;
}

Same Pattern (Collision/Cancellation): - Remove All Adjacent Duplicates (LC 1047) - Remove All Adjacent Duplicates II (LC 1209) - Removing Stars From String (LC 2390)

Stack Simulation: - Car Fleet (LC 853) - Daily Temperatures (LC 739) - Online Stock Span (LC 901)

Direction-Based: - Longest Absolute File Path (LC 388)

Happy practicing! 🎯

Note: This problem teaches Stack Pattern 7: Collision/Cancellation! Master this and you understand: (1) element cancellation patterns, (2) chain reaction handling, (3) direction-based interactions, (4) while loop for multiple collisions. This pattern appears in string manipulation, simulation problems, and parsing. Very common at Amazon, Meta! 💪✨