☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Asteroid Collision

Medium TUF ID 967 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array asteroids of non-zero integers describing asteroids in a row. The absolute value is the asteroid’s size; the sign is its direction (positive moves right, negative moves left). All asteroids move at the same speed.

When two asteroids meet, the smaller one explodes. If both are the same size, both explode. Two asteroids moving in the same direction never meet. Return the asteroids that remain after all collisions, in their original left-to-right order.

Constraints: 0 ≤ n ≤ 10^4, -1000 ≤ asteroids[i] ≤ 1000, asteroids[i] ≠ 0.

Example 1

asteroids = [5, 10, -5]
answer    = [5, 10]        // -5 hits 10 and explodes; 5 and 10 move the same way

Example 2

asteroids = [10, 2, -5]
answer    = [10]           // -5 destroys 2, then meets 10 and explodes

Example 3

asteroids = [-2, -1, 1, 2]
answer    = [-2, -1, 1, 2] // the left group flies left, the right group flies right

The key observation is about which pairs can ever meet. An asteroid moving left at index j can only meet something to its left that is moving right. An asteroid moving right never catches anything ahead of it, and a left-mover on the left of a right-mover ([-3, 4]) is flying away from it. So the only colliding pattern is “positive immediately followed, after the dust settles, by negative”.

Approach 1: Brute force, simulate one collision at a time

Intuition. Treat the row as a list and keep looking for an adjacent pair (positive, negative). That pair is guaranteed to collide, because nothing sits between them. Resolve it by deleting the loser (or both), and start looking again. When no such pair is left, nothing will ever collide again, so the list is the answer.

Does it matter which colliding pair we resolve first? No. Two different adjacent colliding pairs involve disjoint asteroids, so resolving one does not change the outcome of the other. Picking the leftmost pair every time is simply a convenient, deterministic choice.

Algorithm.

  1. Copy the array into a list.
  2. Repeat until a full scan changes nothing:
    • Find the first index i with list[i] > 0 and list[i + 1] < 0.
    • If list[i] is bigger, remove list[i + 1]; if smaller, remove list[i]; if equal, remove both.
  3. Return the list as an array.
static int[] bruteForce(int[] asteroids) {
    List<Integer> list = new ArrayList<>();
    for (int a : asteroids) list.add(a);
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i + 1 < list.size(); i++) {
            int left = list.get(i), right = list.get(i + 1);
            if (left > 0 && right < 0) {                  // the only pattern that can collide
                if (left > -right) list.remove(i + 1);
                else if (left < -right) list.remove(i);
                else { list.remove(i + 1); list.remove(i); }
                changed = true;
                break;
            }
        }
    }
    int[] res = new int[list.size()];
    for (int i = 0; i < res.length; i++) res[i] = list.get(i);
    return res;
}

Complexity. Time O(n^2): every collision removes at least one asteroid, so there are at most n collisions, and each one costs a scan plus an ArrayList removal, both O(n). Space O(n) for the list.

Note the call list.remove(i + 1). On a List<Integer>, passing an int picks remove(int index), which is what we want. Passing an Integer would pick remove(Object) and delete by value instead, a classic Java trap.

Approach 2: Optimal, a stack of survivors

Intuition. Process the asteroids from left to right and keep a stack of everything that has survived so far. The stack has a useful shape: once a left-mover is on the stack, everything below it is also a left-mover or already settled, because it survived every right-mover to its left.

When a new asteroid a arrives:

Each asteroid is pushed at most once and popped at most once, which is where the linear time comes from. The stack is exactly the “survivors so far” list from the brute force, but we never rescan anything.

Algorithm.

  1. Create an empty stack.
  2. For each asteroid a, set alive = true, then while alive, a < 0, and the top of the stack is positive:
    • top < -a: pop the top and continue.
    • top == -a: pop the top and set alive = false.
    • top > -a: set alive = false.
  3. If a is still alive, push it.
  4. Pop the stack into the result array from the back, so the bottom of the stack ends up first.
static int[] optimal(int[] asteroids) {
    Deque<Integer> st = new ArrayDeque<>();
    for (int a : asteroids) {
        boolean alive = true;
        while (alive && a < 0 && !st.isEmpty() && st.peek() > 0) {
            int top = st.peek();
            if (top < -a) st.pop();                       // top explodes, a keeps moving left
            else if (top == -a) { st.pop(); alive = false; }   // both explode
            else alive = false;                           // a explodes
        }
        if (alive) st.push(a);
    }
    int[] res = new int[st.size()];
    for (int i = res.length - 1; i >= 0; i--) res[i] = st.pop();
    return res;
}

Dry run on asteroids = [10, 2, -5]:

a stack before what happens stack after
10 [] right-mover, push [10]
2 [10] right-mover, push [10, 2]
-5 [10, 2] 2 < 5, pop 2; then 10 > 5, -5 explodes [10]

Result [10].

Complexity. Time O(n): every asteroid is pushed at most once and popped at most once, so the total work of all the inner while loops is bounded by n. Space O(n) for the stack in the worst case (for example, all asteroids moving right).

ArrayDeque.push and pop work on the head of the deque, so popping returns the most recently pushed survivor first. That is why the final loop fills res from the last index down to 0.

Edge cases and pitfalls