Skip to main content

735. Asteroid Collision

medium

Simulate asteroids moving in opposite directions and destroying each other on impact. A 'looks like simulation' problem that's secretly a stack with crisp collision rules.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

Input
asteroids = [5,10,-5]
Output
[5,10]

Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2

Input
asteroids = [8,-8]
Output
[]

Explanation: The 8 and -8 collide exploding each other.

Example 3

Input
asteroids = [10,2,-5]
Output
[10]

Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Collisions only happen between a right-mover on the stack top and an incoming left-mover. Same direction or 'left then right' never collide.

Hint 2

Pop while the top of the stack is positive and smaller than abs(incoming) — incoming wins, top explodes.

Hint 3

If sizes are equal, both die: pop top AND skip pushing incoming.

Hint 4

If top is positive and bigger, incoming dies — skip it.

Solution approach

Reveal approach

Stack simulation. Iterate asteroids left to right with a stack of survivors. For each a: assume 'alive = true'. While alive AND stack non-empty AND stack.top() > 0 AND a < 0 (collision condition), compare absolute values: if |stack.top()| < |a|, pop and continue (a destroys top, keep checking); if |stack.top()| == |a|, pop and set alive = false (both explode); if |stack.top()| > |a|, set alive = false (a is destroyed, top survives). If alive after the inner loop, push a. Return the stack. O(n) time amortized (each asteroid is pushed and popped at most once) and O(n) space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • simulation
  • array

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Asteroid Collision and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →