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.

Asteroid Collision - LeetCode Solution

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.

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

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. The collision resolves by comparing sizes and popping smaller asteroids from the stack until the current asteroid is either destroyed or added to the stack. This approach simulates collisions in a single pass.

Optimal Approach

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.

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.

Solution

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

1

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.

2

Iterate Through Asteroids and Resolve Collisions with Stack Top

5for 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)

Objective

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

Key Insight

Collisions only happen when a right-moving asteroid (positive) is on the stack top and the current asteroid is moving left (negative). The algorithm compares sizes and pops smaller asteroids from the stack until the current asteroid is destroyed or can be safely added. The use of a while loop with conditions ensures all relevant collisions are resolved before moving on.

Interview Quick-Check

Core Logic

The while loop continues popping smaller right-moving asteroids from the stack until the current left-moving asteroid is either destroyed or can be appended.

State & Boundaries

The loop condition ensures collisions are only checked when the top asteroid moves right and the current asteroid moves left.

Common Pitfalls & Bugs

Failing to break after equal size collision causes incorrect multiple removals; the break ensures correct termination.

Complexity

Each asteroid is pushed and popped at most once, ensuring O(n) time complexity.

3

Return the Stack as the Final State of Asteroids

16	`return stack`

Objective

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

Key Insight

The stack now contains only asteroids that have survived all collisions in the correct order, so returning it directly provides the final answer.

Interview Quick-Check

Core Logic

Returning the stack directly reflects the final state after all collision simulations.

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).

Line 3 Core

stack = []

Initialize an empty stack to hold surviving asteroids.

The stack is essential to simulate collisions efficiently by storing right-moving asteroids that may collide with incoming left-moving asteroids.

Line 8 Core

stack.pop()

Remove the smaller top asteroid from the stack.

Popping the smaller asteroid simulates its destruction, allowing the current asteroid to continue colliding with others if necessary.

Line 10 Core

if stack[-1] == -a:

Check if the top asteroid and current asteroid are equal in size (absolute value).

Equal-sized asteroids destroy each other, so both must be removed from consideration.

Line 11 Core

stack.pop()

Remove the top asteroid from the stack due to equal size collision.

Popping the top asteroid simulates mutual destruction when sizes are equal.

Line 14 Core

stack.append(a)

Add the current asteroid to the stack if no collision destroyed it.

Appending the current asteroid means it survived all collisions and is now part of the active asteroid sequence.

Line 7 Core

if stack[-1] < -a:

Compare sizes: if top asteroid is smaller than current asteroid's absolute size.

Determining which asteroid explodes depends on size comparison; smaller asteroids are destroyed in collisions.

Line 9 Core

continue

Continue the while loop to check for further collisions.

The continue statement ensures the current asteroid is compared against the next asteroid on the stack, simulating multiple sequential collisions.

Line 16 Core

return stack

Return the stack representing the final state of asteroids after all collisions.

The stack contains all surviving asteroids in the correct order, so returning it provides the final answer.

Line 5 Standard

for a in asteroids:

Begin iterating over each asteroid in the input list.

Processing asteroids sequentially allows the algorithm to simulate collisions in the order they occur along the line.

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?

Because the stack maintains only right-moving asteroids that have not collided yet, and collisions occur only between a right-moving asteroid and a left-moving asteroid. The top of the stack represents the most recent right-moving asteroid that could collide with the current left-moving asteroid, so resolving collisions with it suffices.

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`

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)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize an Empty Stack to Track Active Asteroids

Iterate Through Asteroids and Resolve Collisions with Stack Top

Return the Stack as the Final State of Asteroids

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.