← DSA Atlas
Dedicated problem page · #735

Asteroid Collision

MediumStack and Expression ProcessingCollision-resolution stackStack
Solve on LeetCode ↗
735
MediumStack and Expression ProcessingStackCollision-resolution stack

Asteroid Collision

Given an array asteroids where each value's absolute size is its mass and its sign is its direction (positive means moving right, negative means moving left), simulate their collisions. All asteroids move at the same speed. Two asteroids collide only when a right-moving one is followed by a left-moving one; the smaller explodes, and if they are equal both explode. Return the state of the asteroids after all collisions.

Open official problem prompt ↗
In plain English

Determine which asteroids remain after all direction-based collisions resolve.

Picture it like this

Like cars merging onto a one-lane road: only a car going right that is immediately in front of an oncoming left car can crash, and the lighter one is wrecked.

Example
Input
asteroids = [5, 10, -5]
Output
[5, 10]
Why
The -5 meets the right-moving 10; since 10 > 5, the -5 explodes and 5 and 10 (both never colliding, since 5 is left of 10 and same direction) survive.
Constraints
2 <= asteroids.length <= 10^4-1000 <= asteroids[i] <= 1000asteroids[i] != 0
Pattern lesson

See the pattern, then code

Collision-resolution stack
Recognition clue

A right-mover meeting a left-mover resolves against the most recently surviving right-mover — a last-in-first-out interaction — which points to a stack of survivors.

↗
Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. Only a positive asteroid on top of the stack can be threatened by an incoming negative asteroid; resolve that pairwise duel repeatedly until the incoming asteroid either explodes, survives, or annihilates its opponent.

New words, made simpleKnow these before the algorithm
Direction by sign
Positive moves right, negative moves left; a collision needs a positive to the left of a negative.
Survivor stack
The stack holds asteroids that have not (yet) been destroyed, in left-to-right order.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Repeated array passes

Re-scanning after every removal is wasteful and quadratic.

Scan the array removing colliding pairs until no change.

Time O(n^2)Space O(1)
Best choiceSingle-pass survivor stack

Every asteroid is pushed and popped at most once, giving linear time with clean collision logic.

Resolve each incoming left-mover against right-movers on top until it settles.

Time O(n)Space O(n)
The rule we keep true

Invariant

The stack always contains the set of surviving asteroids consistent with all collisions among the elements processed so far, with any negative asteroids only at the bottom-left where nothing can hit them.

Why this is correct

Reasoning

A collision requires a positive on the stack top and a negative incoming; resolving that single duel either destroys the incoming asteroid, the top, or both. Repeating the duel against successive tops handles chain reactions, and once no positive top remains the incoming negative can never collide again, so pushing it is safe.

The algorithm in three movesSay these aloud before coding
1Iterate asteroids left to right with a stack of survivors

push 5 -> [5]

2For a left-mover, while the top is a right-mover, compare magnitudes

push 10 -> [5,10]

3Pop the smaller (or both on a tie) and stop when the incoming one dies or wins

-5 vs 10: 10>5 so -5 explodes -> [5,10]

4Push the incoming asteroid if it is still alive

5Return the stack

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
50
101
-52
1 · Read5
2 · AskLeft-mover?
3 · Update statestack=[5]
4 · ResultPositive, no collision, push
Key takeaway

The incoming -5 collides with the top 10 and is destroyed.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-15Collision resolution loop

    Only runs when the incoming asteroid moves left and the top moves right — the sole collision case.

  2. 2
    Lines 8-10Top is smaller

    Pop the destroyed top and continue so the incoming asteroid can face the next survivor (chain reaction).

  3. 3
    Lines 11-14Tie or top wins

    Equal magnitudes destroy both; a larger top destroys only the incoming asteroid — either way alive becomes False.

  4. 4
    Lines 16-17Push survivor

    If the asteroid outlived every collision, it joins the stack of survivors.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • All same direction, e.g. [1,2,3] or [-1,-2,-3] — no collisions
  • Equal-magnitude head-on, e.g. [8,-8] — both explode to []
  • A left-mover with an empty or all-negative stack, e.g. [-2,-1,1,2]
  • Chain reactions, e.g. [10,2,-5] where -5 destroys 2 then loses to 10
!

Common beginner mistakes

  • Pushing the negative asteroid before fully resolving all collisions
  • Using continue vs break incorrectly and skipping a chain reaction
  • Forgetting the equal-magnitude case where both asteroids explode
  • Colliding two same-direction asteroids, which never actually collide
Check your understanding

Why can a negative asteroid never collide once the stack top is negative or empty?

More in Stack and Expression Processing

#20Valid ParenthesesMatching stack for bracket pairs#71Simplify PathStack of path components#150Evaluate Reverse Polish NotationOperand stack for postfix evaluation#155Min StackStack augmented with running minimum#224Basic CalculatorStack for parenthesized sign context#227Basic Calculator IIStack with deferred multiply/divide