Asteroid Collision
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
We have an array of asteroids represented by integers. Each asteroid's absolute value is its size, and its sign represents its direction (positive means right, negative means left). All asteroids move at the same speed. When two asteroids collide, the smaller one explodes; if equal size, both explode. Two asteroids moving in the same direction never collide. Return the state of asteroids after all collisions.
Example 1
- Input
- asteroids = [8,3,-6]
- Output
- [8]
- Why
- 3 and -6 collide, 6 wins. Then 8 and -6 collide, 8 wins. Only 8 remains.
Example 2
- Input
- asteroids = [8,-8]
- Output
- []
- Why
- Both asteroids are the same size, so both explode.
Example 3
- Input
- asteroids = [7,3,-4]
- Output
- [7]
- Why
- 3 and -4 collide, 4 wins. Then 7 and -4 collide, 7 wins. Only 7 remains.
Constraints
- 2 <= asteroids.length <= 10^4
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
How to think about it
Updated 2026-09-29Collisions can only occur when a right-moving asteroid (`> 0`) is followed somewhere to its right by a left-moving asteroid (`< 0`). Right-moving asteroids survive unconditionally until a left-mover enters. Treating survived asteroids as a stack allows each left-mover to smash sequentially into previous right-movers until it either shatters, ties and mutual-destructs, or exhausts all right-movers and survives.
Approaches, worst first
Repeated pairwise search and array compaction
time O(n^2) · space O(1)
Search the array for adjacent pairs `(pos, neg)`. Resolve their collision in place, delete the exploded elements, shift the array, and repeat until no adjacent right-left pairs remain. Array deletions and re-indexing cost quadratic time in the worst case.
Stack-based collision resolutionWrite this one
time O(n) · space O(n)
Iterate through asteroids. If an asteroid moves right, push it. If it moves left, compare its size against right-moving tops on the stack: pop smaller tops, destroy both on tie, or let the left-mover explode. If no right-movers remain, push the left-mover to the stack. Elements in the stack never collide again.
Where people lose marks · 3
- Assuming negative asteroids collide with leftward neighbors: a negative asteroid preceding a positive asteroid moves away from it (`<- [neg] [pos] ->`), so they never collide.
- Equal size collision: when `top == abs(current)`, both asteroids must be destroyed; forgetting to pop the top or accidentally pushing the current asteroid keeps a dead asteroid alive.
- Overlooking survival of negative asteroids: if a left-moving asteroid destroys all right-movers on the stack, it must be pushed to the stack as a survivor.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .