Asteroid Collision

This question feels like a game, and that is the fun part. Asteroids fly and crash into each other. The trick is to notice that only the most recent asteroid on one side can take the next hit. That is a perfect job for a stack. So the interviewer is checking if you can model a chain of events cleanly.

🎯 The Problem

You get a row of asteroids as numbers. You return the asteroids that survive all the crashes.

• The size of each number is how big the asteroid is.
• The sign is the direction. Positive moves right, negative moves left.
• All of them move at the same speed.
• A crash happens only when a right-mover meets a left-mover. So a positive number followed by a negative number can collide.
• In a crash the smaller asteroid explodes. Same size means both explode.
• Two asteroids moving the same way never meet, so they never crash.

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

Explanation: 10 moves right and -5 moves left, so they meet.
10 is bigger than 5, so -5 explodes and 10 survives.
5 and 10 both move right, so they never collide.

Here is the row of asteroids with their directions. Watch the spot where 10 meets -5.

🐢 Approach 1: Repeated Passes (Brute Force)

Scan the whole row, resolve one crash, then start over from the beginning.

The idea:

• Walk the row looking for a positive number right before a negative one.
• Resolve that crash and remove whoever explodes.

How it works:

• After a crash, restart the scan from the front.
• Removing asteroids can create a brand new neighbor pair that now collides.
• Keep scanning until a full pass finds no crash.

Why it is weak:

• Every single crash makes you rescan the whole row.
• Many crashes means many full passes.
• Time grows toward O(n²). You redo work you already did.

Here is the repeated-pass code:

def asteroid_collision(asteroids):
    changed = True
    while changed:
        changed = False
        result = []
        i = 0
        while i < len(asteroids):
            if i + 1 < len(asteroids) and asteroids[i] > 0 and asteroids[i + 1] < 0:
                changed = True
                if asteroids[i] > -asteroids[i + 1]:
                    result.append(asteroids[i])
                elif asteroids[i] < -asteroids[i + 1]:
                    result.append(asteroids[i + 1])
                i += 2
            else:
                result.append(asteroids[i])
                i += 1
        asteroids = result
    return asteroids

⚡ Approach 2: One Pass With a Stack (Best)

The idea in one line: keep a stack of survivors, since only the newest survivor on top can take the next hit.

The idea:

• A stack is a pile where you add and remove from the top.
• The top holds the newest survivor, the one that can be hit next.

How a crash is handled:

• A crash needs the top to be positive and the current asteroid to be negative.
• Compare absolute sizes, the number without its sign.
• Top smaller: pop it, the current asteroid keeps going, so loop.
• Same size: pop the top and drop the current one.
• Top bigger: drop the current one.

How it finishes:

• If the current asteroid survives every crash, push it.
• At the end the stack holds the survivors in order.

Why it is fast:

• Each asteroid is pushed at most once and popped at most once.
• So the whole thing is one pass, which is O(n).

Here is the stack changing as we process [5, 10, -5]. The stack always holds the current survivors.

Steps to Solve

1. Create an empty stack to hold surviving asteroids.
2. Go through each asteroid in order.
3. Assume the current asteroid is alive. While the stack top is positive and the current asteroid is negative, a crash can happen.
4. Compare absolute sizes. Pop the smaller one. If equal, pop the top and mark the current one dead too.
5. If the top is bigger, the current asteroid dies. Stop the loop.
6. If the current asteroid is still alive after the loop, push it onto the stack.
7. After the scan, the stack holds the survivors in order.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int asteroids[] = {5, 10, -5};
    int n = 3;
    int stack[100000];
    int top = -1;  // stack is empty

    for (int i = 0; i < n; i++) {
        int cur = asteroids[i];
        int alive = 1;
        // crash only when top moves right and cur moves left
        while (alive && top >= 0 && stack[top] > 0 && cur < 0) {
            if (stack[top] < -cur) {       // top is smaller, it explodes
                top--;
            } else if (stack[top] == -cur) { // same size, both explode
                top--;
                alive = 0;
            } else {                        // top is bigger, cur explodes
                alive = 0;
            }
        }
        if (alive) stack[++top] = cur;  // current asteroid survives
    }

    printf("[");
    for (int i = 0; i <= top; i++) {
        printf("%d", stack[i]);
        if (i < top) printf(", ");
    }
    printf("]\n");
    return 0;
}

[5, 10]

#include <iostream>
#include <vector>
using namespace std;

vector<int> asteroidCollision(vector<int>& asteroids) {
    vector<int> stack;  // surviving asteroids
    for (int cur : asteroids) {
        bool alive = true;
        // crash only when top moves right and cur moves left
        while (alive && !stack.empty() && stack.back() > 0 && cur < 0) {
            if (stack.back() < -cur) {        // top smaller, it explodes
                stack.pop_back();
            } else if (stack.back() == -cur) { // same size, both explode
                stack.pop_back();
                alive = false;
            } else {                          // top bigger, cur explodes
                alive = false;
            }
        }
        if (alive) stack.push_back(cur);  // current asteroid survives
    }
    return stack;
}

int main() {
    vector<int> asteroids = {5, 10, -5};
    vector<int> result = asteroidCollision(asteroids);
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i + 1 < result.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[5, 10]

import java.util.ArrayDeque;
import java.util.Deque;

public class AsteroidCollision {
    public static int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();  // survivors
        for (int cur : asteroids) {
            boolean alive = true;
            // crash only when top moves right and cur moves left
            while (alive && !stack.isEmpty() && stack.peek() > 0 && cur < 0) {
                if (stack.peek() < -cur) {        // top smaller, it explodes
                    stack.pop();
                } else if (stack.peek() == -cur) { // same size, both explode
                    stack.pop();
                    alive = false;
                } else {                          // top bigger, cur explodes
                    alive = false;
                }
            }
            if (alive) stack.push(cur);  // current asteroid survives
        }
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();  // bottom of stack ends up first
        }
        return result;
    }

    public static void main(String[] args) {
        int[] asteroids = { 5, 10, -5 };
        int[] result = asteroidCollision(asteroids);
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < result.length; i++) {
            sb.append(result[i]);
            if (i + 1 < result.length) sb.append(", ");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

[5, 10]

def asteroid_collision(asteroids):
    stack = []  # surviving asteroids
    for cur in asteroids:
        alive = True
        # crash only when top moves right and cur moves left
        while alive and stack and stack[-1] > 0 and cur < 0:
            if stack[-1] < -cur:        # top smaller, it explodes
                stack.pop()
            elif stack[-1] == -cur:     # same size, both explode
                stack.pop()
                alive = False
            else:                       # top bigger, cur explodes
                alive = False
        if alive:
            stack.append(cur)           # current asteroid survives
    return stack


asteroids = [5, 10, -5]
print(asteroid_collision(asteroids))

[5, 10]

function asteroidCollision(asteroids) {
  const stack = []; // surviving asteroids
  for (const cur of asteroids) {
    let alive = true;
    // crash only when top moves right and cur moves left
    while (alive && stack.length && stack[stack.length - 1] > 0 && cur < 0) {
      const top = stack[stack.length - 1];
      if (top < -cur) {        // top smaller, it explodes
        stack.pop();
      } else if (top === -cur) { // same size, both explode
        stack.pop();
        alive = false;
      } else {                 // top bigger, cur explodes
        alive = false;
      }
    }
    if (alive) stack.push(cur); // current asteroid survives
  }
  return stack;
}

const asteroids = [5, 10, -5];
console.log(asteroidCollision(asteroids));

[ 5, 10 ]

Let us read the Python version line by line so the collision logic is clear.

stack = [] starts an empty list that holds the survivors so far. The newest survivor is always at the end, and that is the one that can take the next hit.

for cur in asteroids: walks through every asteroid in order.

alive = True assumes the current asteroid lives. We will turn this off only if it explodes.

while alive and stack and stack[-1] > 0 and cur < 0: is the heart of it. A crash needs the top to move right, which means stack[-1] > 0, and the current asteroid to move left, which means cur < 0. If any of these is false, no crash, so we leave the loop.

if stack[-1] < -cur: compares sizes. Here -cur is the size of the left-mover, because cur is negative. If the top is smaller, the top explodes, so stack.pop() removes it. The current asteroid lives on and the loop checks the new top.

elif stack[-1] == -cur: handles the tie. Same size means both explode. We pop the top and set alive = False.

else: means the top is bigger. So the current asteroid explodes. We set alive = False and the loop ends.

if alive: stack.append(cur) pushes the current asteroid only if it survived every crash. After the full scan, the list holds the survivors in their original left-to-right order.

⏱️ Time and Space Complexity

The naive repeated-pass idea rescans the whole row after each crash, so it drifts to O(n²) time. The stack version pushes and pops each asteroid at most once. So it runs in O(n) time. The stack can hold up to n asteroids, so it needs O(n) extra memory.

🧩 Key Takeaways

• ✅ Sign means direction. Positive moves right and negative moves left.
• ✅ A crash happens only when the stack top is positive and the current asteroid is negative.
• ✅ Compare absolute sizes. The smaller one explodes, and equal sizes blow up both.
• ✅ A surviving current asteroid may keep crashing into the new top, so loop until it is settled.
• ✅ Each asteroid is pushed and popped at most once, so the whole pass is O(n).

🚀 What’s Next?

• Basic Calculator II
• Largest Rectangle in Histogram