How do you solve Asteroid Collision?

Iterate through the asteroids array. For each asteroid, while the stack is non-empty and the top asteroid is moving right and the current asteroid is moving left, compare their sizes. Pop the smaller asteroid. If sizes are equal, pop the top and discard the current. If the current asteroid survives all collisions, push it onto the stack. Return the stack as the final state.

Asteroid Collision

Q: What is the time complexity of Asteroid Collision?

O(n). Each asteroid is pushed and popped at most once from the stack, resulting in linear time complexity.

Q: What pattern does Asteroid Collision use?

The Pattern: Stack (Collision Simulation) The Heuristic: Use a stack to track active right-moving asteroids; when a left-moving asteroid arrives, resolve collisions by popping smaller right-moving asteroids until the current asteroid is destroyed or can be safely pushed, effectively simulating all collisions in a single pass.

Medium Monotonic Stack

Problem

Given an array of integers representing asteroids moving along a line, return the state of the asteroids after all collisions, where positive values move right and negative values move left, and collisions cause smaller asteroids to explode or both to explode if equal.

2 ≤ asteroids.length ≤ 10⁴
−1000 ≤ asteroids[i] ≤ 1000
asteroids[i] != 0

Example

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

Output: [5, 10]

Process the asteroids from left to right using a stack. The asteroid 5 moves right and is added to the stack. Next, 10 also moves right and is added to the stack because asteroids moving in the same direction do not collide. When -5 appears, it moves left and collides with the top of the stack, which is 10. Since 10 > 5 (the absolute value of -5), the -5 asteroid explodes. No further collisions occur, so the final state of the stack is [5, 10].

Approach

Straightforward Solution

A brute-force approach would simulate the movement step-by-step, checking for collisions at each time unit, which is inefficient and can be O(n^2) in the worst case.

Core Observation

Collisions only occur when a right-moving asteroid meets a left-moving asteroid. Asteroids moving in the same direction never collide. This means collisions happen only when a positive asteroid is followed by a negative asteroid.

Path to Optimal

Preview

The key insight is to use a stack to keep track of asteroids moving right that have not yet collided. When a left-moving asteroid arrives, it collides with the top of the stack if that asteroid is moving right…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the asteroids array. For each asteroid, while the stack is non-empty and the top asteroid is moving right and the current asteroid is moving left, compare their sizes…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each asteroid is pushed and popped at most once from the stack, resulting in linear time complexity.

Space

O(n)

The stack can hold up to all asteroids in the worst case, so auxiliary space is linear in the input size.

Pattern Spotlight

Stack (Collision Simulation)

Use a stack to track active right-moving asteroids; when a left-moving asteroid arrives, resolve collisions by popping smaller right-moving asteroids until the current asteroid is destroyed or can be safely pushed, effectively simulating all collisions in a single pass.

Solution

Python

1class Solution:
  def asteroidCollision(self, asteroids: List[int]) -> List[int]:
      stack = []
4
      for a in asteroids:
          while stack and stack[-1] > 0 and a < 0:
              if stack[-1] < -a:
                  stack.pop()
                  continue
              if stack[-1] == -a:
                  stack.pop()
              break
          else:
              stack.append(a)
15
      return stack

Step-by-Step Solution

Initialize an Empty Stack to Track Active Asteroids

3	`stack = []`

Objective

To create a data structure that will hold asteroids that have survived collisions so far.

Key Insight

A stack naturally models the sequence of right-moving asteroids that can potentially collide with incoming left-moving asteroids. It allows efficient last-in, first-out access to the most recent asteroid that could collide.

Interview Quick-Check

Core Logic

The stack holds only asteroids that have not been destroyed and are candidates for collision with future asteroids.

Common Pitfalls & Bugs

Using a queue or list without stack semantics would complicate collision resolution and increase time complexity.

Iterate Through Asteroids and Resolve Collisions with Stack Top

To process each asteroid and simulate collisions by comparing with the top of the stack when conditions for collision exist.

Return the Stack as the Final State of Asteroids

To output the surviving asteroids after all collisions have been resolved.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 6 Critical

while stack and stack[-1] > 0 and a < 0:

Check if there is a potential collision: stack not empty, top asteroid moving right, current asteroid moving left.

This conditional is the critical gatekeeper that triggers collision resolution only when a right-moving asteroid meets a left-moving asteroid, ensuring correctness and efficiency.

Line 12 Critical

break

Break out of the while loop after equal size collision.

Breaking here is critical to avoid incorrectly adding a destroyed asteroid to the stack, preserving the integrity of the simulation.

Line 13 Critical

else:

Append the current asteroid to the stack if it survived all potential collisions or if it is a right-moving asteroid that cannot collide with previous ones.

The while-else construct runs the else block only if the loop finishes without hitting a break. This happens when the asteroid survives all collision checks, or when no collision was possible in the first place (such as when the asteroid is moving right).

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does the algorithm only need to compare the current left-moving asteroid with the top of the stack and not with all asteroids in the stack?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Asteroid Collision from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Asteroid Collision drill

or drill a free problem

1	`class Solution:`
2	`def asteroidCollision(self, asteroids: List[int]) -> List[int]:`
3	`stack = []`
4
5	`for a in asteroids:`
6	`while stack and stack[-1] > 0 and a < 0:`
7	`if stack[-1] < -a:`
8	`stack.pop()`
9	`continue`
10	`if stack[-1] == -a:`
11	`stack.pop()`
12	`break`
13	`else:`
14	`stack.append(a)`
15
16	`return stack`