MediumArrayStackSimulationUpdated Sep 2026

735. Asteroid Collision

Asked at Amazon, OpenAI, Salesforce, Visa and 1 more

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

5

Problem

You are given a list of asteroids in a row. Each asteroid is an integer. The sign tells you which way it moves: positive means it moves right, negative means it moves left. The absolute value is its size. All asteroids move at the same speed.

When a right-moving asteroid and a left-moving asteroid meet, they collide. The smaller one explodes. If they are the same size, both explode. Asteroids moving the same way never meet, because they keep the same distance apart.

Return the list of asteroids that are still alive after all collisions finish, in their original left-to-right order.

Who meets whom

asteroids510-5012→←10 moves right, -5 moves left, so they are on acollision courseafter5100110 is bigger, so -5 explodes and the survivors are [5,10]
Only a right-mover followed by a left-mover can collide; same-direction asteroids never meet.

Constraints

  • ●2 <= asteroids.length <= 10^4
  • ●-1000 <= asteroids[i] <= 1000
  • ●asteroids[i] != 0

Examples

Example 1
Inputasteroids = [5,10,-5]
Output[5,10]
WhyThe 10 moves right and the -5 moves left, so they meet. 10 is bigger, so -5 explodes. The 5 and the 10 both move right, so they never touch.
Example 2
Inputasteroids = [8,-8]
Output[]
WhyThe 8 and the -8 move toward each other and have the same size, so both explode. Nothing is left.
Example 3
Inputasteroids = [10,2,-5]
Output[10]
WhyThe -5 first meets the 2. Since 5 > 2, the 2 explodes. The -5 keeps going left and meets the 10. Now 10 > 5, so the -5 explodes. Only the 10 survives.

Asked At

5 companies
CompanyDifficulty
AmazonMediumView all Amazon questions →
OpenAIMediumView all OpenAI questions →
SalesforceMediumView all Salesforce questions →
VisaMediumView all Visa questions →
DE ShawMediumView all DE Shaw 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

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).

Stack simulation

stack510frontbackPush 5, then push 10 — both move right, so nocollision yetstack510frontback-5 arrives: top is 10 > 0, so compare sizes — 5 < 10,the -5 explodesstack510frontbackNothing left to fight, so the final stack [5, 10] isthe answerwhile stack top > 0 and current < 0: |cur| > top → pop top, keep fighting |cur| < top → cur dies equal → both die
Keep the survivors on a stack; a left-mover fights the right-movers on top until one side dies.
ComplexityTime O(n)Space O(n)Each asteroid is pushed and popped at most once, and the stack can hold every asteroid in the worst case.

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

O(n) time
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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Asteroid Collision?

Asteroid Collision is asked at Amazon, OpenAI, Salesforce, Visa, DE Shaw. 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.