Skip to main content
CodePeetCodePeet
CodePeet 250

Asteroid Collision

MEDIUMProblemSolveExternal Links

Description

We are given an array asteroids of integers representing asteroids in a row. The indices represent their relative position in space.

For each asteroid:

  • The absolute value represents its size.
  • The sign represents its direction: positive means moving right, negative means moving left.
  • All asteroids move at the same speed.

Collision rules:

  • If two asteroids meet (a right-moving asteroid is to the left of a left-moving one), the smaller one explodes.
  • If both are the same size, both explode.
  • Two asteroids moving in the same direction will never meet.

Return the state of the asteroids after all collisions.

Examples

Example 1

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

Output: [5, 10]

Explanation: Asteroid 10 (right) and -5 (left) collide. |10| > |-5|, so -5 explodes. Asteroid 5 and 10 both move right, so they never meet.

Example 2

Input: asteroids = [8, -8]

Output: []

Explanation: Asteroid 8 (right) and -8 (left) collide. |8| = |-8|, so both explode. Nothing survives.

Example 3

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

Output: [10]

Explanation: Asteroid 2 (right) and -5 (left) collide. |-5| > |2|, so 2 explodes. Then 10 (right) and -5 (left) collide. |10| > |-5|, so -5 explodes. Only 10 survives.

Example 4

Input: asteroids = [3, 5, -6, 2, -1, 4]

Output: [-6, 2, 4]

Explanation: The asteroid -6 (size 6, left) destroys both 5 (size 5) and 3 (size 3) as it moves left. Then 2 (right) and -1 (left) collide — 2 wins, -1 explodes. Asteroid 4 moves right and doesn't collide with anything. Final: [-6, 2, 4].

Constraints

  • 2 ≤ asteroids.length ≤ 10⁴
  • -1000 ≤ asteroids[i] ≤ 1000
  • asteroids[i] ≠ 0

Editorial

Brute Force

Intuition

The most direct simulation approach: repeatedly scan the array for collisions, resolve them one at a time, and keep scanning until no more collisions exist.

A collision happens when a positive asteroid (moving right) is immediately followed by a negative asteroid (moving left). They're heading toward each other.

Here's the process:

  1. Scan the array from left to right.
  2. Whenever you find a pair [positive, negative] adjacent to each other, resolve the collision:
    • If |positive| > |negative|: remove the negative asteroid.
    • If |negative| > |positive|: remove the positive asteroid.
    • If equal: remove both.
  3. After resolving one collision, restart the scan because the removal might expose new collisions.
  4. Repeat until a full scan finds no collision.

This is like watching a chain reaction in slow motion — resolve one explosion at a time, then check if the aftermath creates new collisions.

The problem with this approach is that after each collision resolution, we restart the scan. In the worst case (e.g., [1, 2, 3, 4, -5]), the large negative asteroid destroys each positive one in separate passes, leading to O(n) passes each scanning O(n) elements.

Step-by-Step Explanation

Let's trace with asteroids = [3, 5, -6, 2, -1, 4].

Pass 1:

  • Check index 0,1: [3, 5] — both positive (same direction). No collision.
  • Check index 1,2: [5, -6] — positive then negative. Collision! |5| < |-6|, so 5 explodes. Array becomes [3, -6, 2, -1, 4]. Restart.

Pass 2:

  • Check index 0,1: [3, -6] — positive then negative. Collision! |3| < |-6|, so 3 explodes. Array becomes [-6, 2, -1, 4]. Restart.

Pass 3:

  • Check index 0,1: [-6, 2] — negative then positive. Moving away from each other. No collision.
  • Check index 1,2: [2, -1] — positive then negative. Collision! |2| > |-1|, so -1 explodes. Array becomes [-6, 2, 4]. Restart.

Pass 4:

  • Check index 0,1: [-6, 2] — no collision.
  • Check index 1,2: [2, 4] — both positive. No collision.
  • Full scan, no collisions found. Done!

Result: [-6, 2, 4]

Brute Force — Repeated Scan Simulation — Watch how each pass through the array finds and resolves one collision, with the scan restarting after each resolution until the array is stable.

Algorithm

  1. Use a list (dynamic array) to hold the current asteroids.
  2. Set collision_found = true.
  3. While collision_found:
    a. Set collision_found = false.
    b. Scan from left to right (i = 0 to len-2):
    • If asteroids[i] > 0 and asteroids[i+1] < 0 (collision pair):
      • If |asteroids[i]| > |asteroids[i+1]|: remove asteroids[i+1]
      • Else if |asteroids[i]| < |asteroids[i+1]|: remove asteroids[i]
      • Else: remove both
      • Set collision_found = true, break inner loop
  4. Return the remaining asteroids.

Code

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> result(asteroids.begin(), asteroids.end());
        bool collisionFound = true;
        
        while (collisionFound) {
            collisionFound = false;
            for (int i = 0; i < (int)result.size() - 1; i++) {
                if (result[i] > 0 && result[i + 1] < 0) {
                    int right = result[i];
                    int left = abs(result[i + 1]);
                    if (right > left) {
                        result.erase(result.begin() + i + 1);
                    } else if (left > right) {
                        result.erase(result.begin() + i);
                    } else {
                        result.erase(result.begin() + i, result.begin() + i + 2);
                    }
                    collisionFound = true;
                    break;
                }
            }
        }
        return result;
    }
};
class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        result = list(asteroids)
        collision_found = True
        
        while collision_found:
            collision_found = False
            for i in range(len(result) - 1):
                if result[i] > 0 and result[i + 1] < 0:
                    right = result[i]
                    left = abs(result[i + 1])
                    if right > left:
                        result.pop(i + 1)
                    elif left > right:
                        result.pop(i)
                    else:
                        result.pop(i + 1)
                        result.pop(i)
                    collision_found = True
                    break
        return result
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        List<Integer> result = new ArrayList<>();
        for (int a : asteroids) result.add(a);
        
        boolean collisionFound = true;
        while (collisionFound) {
            collisionFound = false;
            for (int i = 0; i < result.size() - 1; i++) {
                if (result.get(i) > 0 && result.get(i + 1) < 0) {
                    int right = result.get(i);
                    int left = Math.abs(result.get(i + 1));
                    if (right > left) {
                        result.remove(i + 1);
                    } else if (left > right) {
                        result.remove(i);
                    } else {
                        result.remove(i + 1);
                        result.remove(i);
                    }
                    collisionFound = true;
                    break;
                }
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case, each pass resolves one collision and we might need up to n-1 passes (e.g., [1, 2, 3, ..., n-1, -n] where the large negative asteroid destroys each positive one, one per pass). Each pass scans up to n elements. Total: O(n × n) = O(n²).

Additionally, array element removal (erase/pop) is O(n) for shifting elements, adding to the cost.

Space Complexity: O(n)

We store a copy of the input array.

Why This Approach Is Not Efficient

The brute force rescans the entire array after every single collision. This is wasteful because a collision at position i can only create new collisions at position i-1 (where the previous right-moving asteroid meets the survivor). We don't need to restart from the beginning.

Another issue: removing elements from the middle of an array is O(n) due to shifting. We're doing O(n) removals, each costing O(n).

Key insight: We can process asteroids left to right, keeping a stack of surviving asteroids. When we encounter a left-moving asteroid, we only need to check if it collides with the top of the stack (the most recent right-moving asteroid). If it destroys the top, we check the new top, and so on. This way, each asteroid is pushed and popped at most once — giving us O(n) total.

Optimal Approach - Stack-Based Single Pass

Intuition

Imagine standing at the left side of space, watching asteroids fly by. You maintain a stack of surviving asteroids as you process them left to right.

For each new asteroid:

  • If it's moving right (positive): No immediate collision possible — it can only collide with future left-moving asteroids. Push it onto the stack.
  • If it's moving left (negative): It might collide with right-moving asteroids already on the stack. Check the stack top:
    • If the stack top is also negative (or stack is empty): no collision, push the new asteroid.
    • If the stack top is positive: COLLISION! Compare sizes:
      • Top is bigger: the new asteroid is destroyed, move to the next asteroid.
      • New asteroid is bigger: pop the top (it's destroyed), and check the next stack element (the left-moving asteroid continues its rampage).
      • Equal size: both destroyed — pop the top and discard the new asteroid.

Think of it like a bowling ball (left-moving asteroid) crashing into a row of pins (right-moving asteroids on the stack). The ball keeps knocking down pins until it either hits a bigger pin, finds a pin the same size (mutual destruction), or clears all the pins.

The stack naturally handles chain reactions: destroying one asteroid exposes the one below, which might also collide.

Step-by-Step Explanation

Let's trace with asteroids = [3, 5, -6, 2, -1, 4].

Step 1: Process 3 (positive, →). Stack is empty, push. Stack: [3].

Step 2: Process 5 (positive, →). Top is 3 (→), same direction. Push. Stack: [3, 5].

Step 3: Process -6 (negative, ←). Top is 5 (→) — COLLISION! |5| < |-6|, 5 is destroyed. Pop 5. Stack: [3]. Check new top: 3 (→) — COLLISION again! |3| < |-6|, 3 is destroyed. Pop 3. Stack: []. Stack empty, no more right-movers to collide with. Push -6. Stack: [-6].

Step 4: Process 2 (positive, →). Top is -6 (←). A left-mover followed by a right-mover — they move apart. Push. Stack: [-6, 2].

Step 5: Process -1 (negative, ←). Top is 2 (→) — COLLISION! |2| > |-1|, -1 is destroyed. Don't push. Stack: [-6, 2].

Step 6: Process 4 (positive, →). Top is 2 (→), same direction. Push. Stack: [-6, 2, 4].

Result: [-6, 2, 4] — processed in a single pass!

Stack-Based Single Pass — Asteroid Collision Resolution — Watch how each asteroid is processed once: right-movers push onto the stack, left-movers collide with the stack top until they're destroyed or the stack has no more right-movers to hit.

Algorithm

  1. Initialize an empty stack.
  2. For each asteroid in the array:
    a. Set alive = true (the current asteroid starts alive).
    b. While alive AND the stack is not empty AND the current asteroid is negative (←) AND the stack top is positive (→):
    • If stack.top() < |current|: Pop the top (it's destroyed). Continue checking.
    • Else if stack.top() == |current|: Pop the top. Set alive = false (mutual destruction).
    • Else (stack.top() > |current|): Set alive = false (current is destroyed).
      c. If alive: push the current asteroid onto the stack.
  3. Return the stack contents (bottom to top) as the result array.

Code

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> stack;
        
        for (int ast : asteroids) {
            bool alive = true;
            
            while (alive && !stack.empty() && ast < 0 && stack.back() > 0) {
                if (stack.back() < -ast) {
                    // Stack top is smaller, it gets destroyed
                    stack.pop_back();
                } else if (stack.back() == -ast) {
                    // Same size, both destroyed
                    stack.pop_back();
                    alive = false;
                } else {
                    // Stack top is bigger, current asteroid destroyed
                    alive = false;
                }
            }
            
            if (alive) {
                stack.push_back(ast);
            }
        }
        
        return stack;
    }
};
class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []
        
        for ast in asteroids:
            alive = True
            
            while alive and stack and ast < 0 and stack[-1] > 0:
                if stack[-1] < -ast:
                    # Stack top is smaller, destroyed
                    stack.pop()
                elif stack[-1] == -ast:
                    # Same size, both destroyed
                    stack.pop()
                    alive = False
                else:
                    # Stack top is bigger, current destroyed
                    alive = False
            
            if alive:
                stack.append(ast)
        
        return stack
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int ast : asteroids) {
            boolean alive = true;
            
            while (alive && !stack.isEmpty() && ast < 0 && stack.peekLast() > 0) {
                if (stack.peekLast() < -ast) {
                    stack.pollLast();
                } else if (stack.peekLast() == -ast) {
                    stack.pollLast();
                    alive = false;
                } else {
                    alive = false;
                }
            }
            
            if (alive) {
                stack.addLast(ast);
            }
        }
        
        int[] result = new int[stack.size()];
        int i = 0;
        for (int val : stack) {
            result[i++] = val;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each asteroid is pushed onto the stack at most once and popped at most once. Even though we have a while loop inside the for loop, the total number of pop operations across the entire algorithm is bounded by n (since each element can only be popped once). By amortized analysis, the total work is O(n).

Worse case example: [-1, -2, -3, 1, 2, 3] — no collisions at all, just n pushes. Or [3, 2, 1, -4] — the -4 destroys 1, 2, 3 in a chain of 3 pops, but those 3 elements were each pushed exactly once and popped exactly once.

Space Complexity: O(n)

In the worst case, all asteroids survive (e.g., all positive or all negative), so the stack holds all n elements.