The O(n) Club: Asteroid Collision: Simulate, Stack, Survive (LeetCode 735)

The O(n) Club: Asteroid Collision—Simulate, Stack, Survive (LeetCode 735)

⚡ TL;DR

Bunch of asteroids, each moving left or right. When they collide, smaller ones explode. Forget brute force—use a stack, keep your sanity, and finish before the sun explodes:

// Java, the stack way:
Stack<Integer> stack = new Stack<>();
for (int a : asteroids) {
    // handle left-moving asteroids with stack.pop and big feelings
}
// What's left in stack is what's left in space

🧠 How Devs Usually Mess This Up

Ah, the classic trap—”I’ll just compare every pair of asteroids!” Please don’t. Nested loops here are a one-way ticket to O(n²) doom and CPU meltdown. Another favorite: mixing up which sign means which direction, so asteroids inexplicably reverse course like indecisive toddlers. Oh, and forgetting the “equal-size kills both” rule—half the Internet seems convinced ties should go to the asteroid with a nice backstory. Wrong. Double obliteration every time.

🔍 What’s Actually Going On

Imagine you’re the bouncer at the intergalactic asteroid club. Every right-mover (positive) strolls right in. Left-movers (negative)? They punch straight for confrontation. The stack is your velvet rope: top is the last right-moving asteroid. If a left-mover shows up, it picks a fight with whoever’s on top, repeated until one gives up or nobody’s left to argue. Stack pops are the sound of rocks meeting their match… and space janitors sighing in relief.

🛠️ PseudoCode

• Start with an empty stack
  Stack<Integer> stack = new Stack<>();
• For each asteroid a in the input:
  • If a > 0 (right-moving), push onto stack. Let it party.
  • If a < 0 (left-moving):
    • While stack isn’t empty and stack.top > 0 and stack.top < |a|: pop (smaller right-movers explode).
    • If after that, stack isn’t empty and stack.top == |a|: pop (both die in mutual explosion).
    • If stack is empty or stack.top < 0: push a (no more fights available).
    • If stack.top > |a|: skip/push nothing (left-mover loses, right-mover high-fives itself).
• Done? Stack holds survivors—in order if you reverse it, so pop them out if you care about the original arrangement.

💻 The Code

import java.util.*;
 public class AsteroidCollision {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            boolean alive = true;
            while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
                int top = stack.peek();
                if (top < -a) {
                    stack.pop(); // Right asteroid is smaller, boom.
                } else if (top == -a) {
                    stack.pop(); // Same size, both vaporized.
                    alive = false;
                } else {
                    alive = false; // Left asteroid loses battle.
                }
            }
            if (alive) {
                stack.push(a);
            }
        }
        // Stack has survivors in reverse; fix the order
        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; --i) {
            res[i] = stack.pop();
        }
        return res;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Direction mistake? Right is positive, left is negative. Ignore this and asteroids will misbehave like bad test data on a Friday.
• Only collide when a right-mover meets a left-mover. No drive-bys from the same direction.
• If asteroids are equal in size, both explode—even if you want a “happy ending.” Sorry.
• Think you need nested loops? Nope. Every asteroid enters and leaves the stack at most once, for beautiful O(n) time.
• Classic edge cases: all left, all right, the lonely single asteroid, or (if you’re spicy) zeros—handle them all the same way. Works out of the box!

🧠 Interviewer Brain-Tattoo

“Every time you reach for a nested loop here, a space rock cries. Simulate like you mean it—O(n) is your wingman.”