Medium
ArrayStackSimulation
Updated Sep 2026

Asteroid Collision

Asked at Amazon, OpenAI, Salesforce

Problem

We are given an array asteroids of integers representing asteroids in a row. The absolute value represents the size and the sign represents the direction (positive = right, negative = 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 explode. Two asteroids moving in the same direction will never meet.

Asked At

CompanyDifficulty
AmazonMediumView all Amazon questions →
OpenAIMediumView all OpenAI questions →
SalesforceMediumView all Salesforce questions →

How to Think About It

1.

Use a stack to simulate the collisions. Iterate through each asteroid. If the current asteroid is moving right (positive), push it onto the stack. If it is moving left (negative), it may collide with asteroids on the stack that are moving right.

2.

Collision logic: while the stack is not empty and the top of the stack is positive (moving right) and the current asteroid is negative (moving left), a collision occurs. Compare their sizes:

  • If |current| > |stack_top|: pop the stack top (it explodes), continue checking the next stack top.
  • If |current| < |stack_top|: current asteroid explodes (do not push). Break.
  • If equal: both explode (pop stack top, do not push current). Break.
3.

Visual walkthrough for [5, 10, -5]:
Push 5, stack=[5]
Push 10, stack=[5, 10]
-5 comes in. Top=10 (positive), -5 (negative): collision. 10 > 5, so -5 explodes. stack=[5, 10].
Result: [5, 10].

4.

Visual walkthrough for [8, -8]:
Push 8, stack=[8]
-8 comes in. Top=8 (positive), -8 (negative): collision. Equal sizes, both explode. stack=[].
Result: [].

5.

Visual walkthrough for [10, 2, -5]:
Push 10, stack=[10]
Push 2, stack=[10, 2]
-5 comes in. Top=2 (positive), -5 (negative): collision. 5 > 2, pop 2. stack=[10]. Top=10 (positive), -5 (negative): collision. 10 > 5, -5 explodes. stack=[10]. Result: [10].

6.

Time: O(n) — each asteroid is pushed and popped at most once. Space: O(n) — the stack in the worst case (all moving right).

Optimal Approach

Initialize an empty stack. For each asteroid in the array:

  1. If asteroid > 0, push it onto the stack.
  2. If asteroid < 0, while the stack is not empty and the top > 0:
    a. If |asteroid| > stack_top: pop the stack (top explodes), continue.
    b. If |asteroid| == stack_top: pop the stack (both explode), break.
    c. If |asteroid| < stack_top: current explodes (do not push), break.
  3. If the stack is empty or the top is negative after the while loop, push the current asteroid.

Walkthrough: [10, 2, -5]

  • stack = []. Push 10. stack = [10].
  • Push 2. stack = [10, 2].
  • -5: top=2>0, 5>2 -> pop 2. stack=[10]. top=10>0, 5<10 -> -5 explodes. stack=[10].
    Result: [10].

Time: O(n). Space: O(n).

What Trips People Up in Real Interviews

1.

Forgetting that a negative asteroid that survives all collisions must still be pushed. After the while loop, if the stack is empty or the top is negative, push the current asteroid. This is handled by the else clause in Python's for/else.

2.

Not handling the case where the current negative asteroid is destroyed by a larger positive one. When |current| < stack_top, break without pushing. Many candidates push anyway, which is wrong.

3.

Confusing the direction convention. Positive = right, negative = left. Two positives never collide (both go right). Two negatives never collide (both go left). Only a positive followed by a negative (left-moving into right-moving) collides.

4.

Trying to use two pointers instead of a stack. Two pointers fail because collisions can cascade (destroying middle elements affects which future asteroids collide). The stack naturally handles this cascading effect.

5.

Off-by-one when both asteroids are equal size. Both must be removed. Pop the stack top and do NOT push the current asteroid. Forgetting to pop the stack top in this case leaves a ghost asteroid.

Solution Code

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        if a > 0:
            stack.append(a)
        else:
            while stack and stack[-1] > 0:
                if abs(a) > stack[-1]:
                    stack.pop()
                elif abs(a) == stack[-1]:
                    stack.pop()
                    break
                else:
                    break
            else:
                stack.append(a)
    return stack

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Asteroid Collision problem?

We are given an array asteroids of integers representing asteroids in a row. The absolute value represents the size and the sign represents the direction (positive = right, negative = 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 explode. Two asteroids moving in the same direction will never meet.

How do you solve Asteroid Collision?

The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

What companies ask Asteroid Collision?

Asteroid Collision is asked at Amazon, OpenAI, Salesforce. It is a medium difficulty problem.

What are common mistakes on Asteroid Collision?
  • Forgetting that a negative asteroid that survives all collisions must still be pushed. After the while loop, if the `stack` is empty or the top is negative, push the current asteroid. This is handled by the `else` clause in Python's `for/else`.
  • Not handling the case where the current negative asteroid is destroyed by a larger positive one. When `|current| < stack_top`, break without pushing. Many candidates push anyway, which is wrong.
  • Confusing the direction convention. Positive = right, negative = left. Two positives never collide (both go right). Two negatives never collide (both go left). Only a positive followed by a negative (left-moving into right-moving) collides.
  • Trying to use two pointers instead of a `stack`. Two pointers fail because collisions can cascade (destroying middle elements affects which future asteroids collide). The `stack` naturally handles this cascading effect.
  • Off-by-one when both asteroids are equal size. Both must be removed. Pop the stack top and do NOT push the current asteroid. Forgetting to pop the stack top in this case leaves a ghost asteroid.