Asteroid Collision

You are given an array asteroids; each value is a moving asteroid. Its magnitude is its size and its sign is its direction: positive moves right, negative moves left. All move at the same speed.

Two asteroids collide only when a right-moving one is immediately followed by a left-moving one. The smaller explodes; if they're the same size, both explode. Same-direction asteroids never collide. Return the state of the asteroids after all collisions.

Hints

· Stuck? Reveal one nudge at a time.

A collision only happens when a right-mover is immediately followed by a left-mover.

Keep a stack of survivors; push right-movers, and let left-movers fight down the stack.

Compare magnitudes: pop a smaller top, annihilate an equal one, or destroy the incoming asteroid.

Common doubts

A right-mover moves away from everything already on the stack, so it never collides on arrival. Only a left-mover can catch up to the right-movers ahead of it.

It might be destroyed during its collisions. Pushing it first would leave a dead asteroid on the stack.

Every asteroid is pushed at most once and popped at most once across the whole run, so total collision work is linear.

Interview follow-ups

· What an interviewer asks next.

The 'immediately adjacent' collision rule breaks; you'd sort collision events by time and process them in order — an event-driven simulation.

Track indices on the stack and record the survivor/destroyer pair at each collision.

Fun facts

This is a discrete-event collision simulation compressed into a single stack pass.
The same 'incoming element cascades through the stack' shape appears in expression evaluation and bracket matching.

Asked at

AmazonGoogleMeta

Frequently Sometimes Occasionally

Example 1

Input: asteroids = [5,10,-5]
Output: [5,10]
10 and -5 collide; 10 survives. 5 and 10 move the same way and never collide.

Example 2

Input: asteroids = [8,-8]
Output: []
8 and -8 are equal size, so both explode.

Constraints

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

Only a right-moving asteroid followed by a left-moving one collides — which is exactly a stack situation: the right-movers pile up, and each incoming left-mover fights its way down the stack until it survives, explodes, or annihilates a match. One pass with a stack resolves every collision.

Prerequisites

Before you start

· Concepts used directly in the solution.

Stack simulation. Using a stack to hold the surviving asteroids as you scan left to right.

Sign as direction. Positive = right, negative = left; magnitude decides who wins.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Collision rules

“When do two asteroids collide?”

Only when a right-mover (positive) is immediately to the left of a left-mover (negative).

“What happens on equal sizes?”

Both explode.

The ideal opening — say it like this

A collision only happens when a right-mover meets a left-mover, so I keep a stack of survivors.

An incoming left-mover collides with positive asteroids on top of the stack, one at a time.

It pops smaller ones, annihilates an equal one, or itself explodes against a larger one.

Understand the problem

Worked example — asteroids = [10, 2, -5]

10 -> push        stack [10]
2  -> push        stack [10, 2]
-5 -> collide with 2: |2| < 5, 2 explodes -> stack [10]
      collide with 10: |10| > 5, -5 explodes
result: [10]

Key observations

1Aha

Only right-then-left collides

A collision requires a positive asteroid immediately followed by a negative one. Same-direction or left-then-right pairs never collide — so a left-mover only ever fights the positive asteroids on the stack.

2Aha

A left-mover cascades down the stack

An incoming negative asteroid can destroy several stacked positives in a row, continuing until it's blocked, annihilated, or destroyed.

3Aha

Linear time

Each asteroid enters the stack once and is removed at most once, so the whole simulation is O(n).

Summary

Key takeaway

Keep a stack of survivors. Push right-movers freely; a left-mover collides with the positive asteroids on top — popping smaller ones, annihilating an equal one, or being destroyed by a larger one. Push it only if it survives. O(n) time.

for a in asteroids:
    alive = true
    while alive and a < 0 and stack and stack.top > 0:
        if stack.top < -a: pop            # top explodes, keep colliding
        elif stack.top == -a: pop; alive=false   # both explode
        else: alive = false               # a explodes
    if alive: push a
return stack