Problem Description

You are given an array asteroids of integers representing asteroids in a row. Each asteroid's position in the array represents its relative position in space.

For each asteroid:

• The absolute value represents its size
• The sign represents its direction (positive = moving right, negative = moving left)
• All asteroids move at the same speed

When two asteroids collide:

• The smaller asteroid explodes and disappears
• If both asteroids are the same size, both explode and disappear
• Asteroids moving in the same direction will never meet

Your task is to find the final state of all asteroids after all possible collisions have occurred.

For example, if you have asteroids [5, 10, -5]:

• The asteroid 10 and -5 collide
• Since 10 is larger than |-5|, the -5 asteroid explodes
• The final state is [5, 10]

Another example with [8, -8]:

• The asteroids 8 and -8 collide
• Since they are the same size, both explode
• The final state is []

The solution uses a stack to simulate the collision process. As we traverse each asteroid from left to right, we check if it will collide with asteroids already in the stack. Right-moving asteroids (positive values) are added directly to the stack. Left-moving asteroids (negative values) may collide with right-moving asteroids in the stack, and we handle these collisions by comparing their sizes and removing destroyed asteroids accordingly.

Intuition

When thinking about this problem, we need to consider when collisions actually happen. Two asteroids collide only when a right-moving asteroid (positive) meets a left-moving asteroid (negative), and the right-moving one must come before the left-moving one in the array.

The key insight is that we're processing asteroids from left to right, simulating their movement through space. At any point in time, we need to keep track of which asteroids are still "alive" and haven't been destroyed by collisions.

A stack is perfect for this because:

1. We process asteroids one by one from left to right
2. A new asteroid can only collide with asteroids that came before it (and survived)
3. When a left-moving asteroid appears, it will first collide with the most recent right-moving asteroid (the one at the top of the stack)

Think of it like this: the stack represents the current state of surviving asteroids. When we encounter a right-moving asteroid (x > 0), it moves away from all previous asteroids, so no collision occurs - we simply add it to our stack.

The interesting case is when we encounter a left-moving asteroid (x < 0). This asteroid moves toward the left, potentially colliding with any right-moving asteroids before it. The collision happens with the closest right-moving asteroid first (which is at the top of our stack). We keep checking collisions and removing destroyed asteroids until either:

• The left-moving asteroid is destroyed (it met a larger right-moving one)
• All right-moving asteroids in its path are destroyed
• It meets another left-moving asteroid (they move in the same direction, no collision)
• The stack becomes empty (no more asteroids to collide with)

This naturally leads to a stack-based simulation where we maintain the surviving asteroids and handle collisions as we process each new asteroid.

Learn more about Stack patterns.

Solution Approach

We use a stack to simulate the asteroid collisions as we traverse the array from left to right. Here's how the implementation works:

For each asteroid x in the array:

Case 1: Right-moving asteroid (x > 0)

• Simply push it onto the stack
• It moves away from all previous asteroids, so no collision occurs
• stk.append(x)

Case 2: Left-moving asteroid (x < 0) This is where collisions may happen. We need to handle multiple scenarios:

First, we check for collisions with right-moving asteroids:

• While the stack is not empty AND the top element is positive (right-moving) AND the top element is smaller than |x|:
  • The right-moving asteroid explodes, so we pop it: stk.pop()
  • Continue checking with the next asteroid in the stack
• This loop continues until we find a right-moving asteroid that's large enough to survive, or until there are no more right-moving asteroids

After the loop, we have three possible situations:

1. Equal-sized collision: If the top of stack equals |x| (i.e., stk[-1] == -x)

   • Both asteroids explode
   • Pop the top element and don't add x to the stack

2. No collision or left-moving asteroid on top: If the stack is empty OR the top element is negative

   • The left-moving asteroid x survives
   • Add it to the stack: stk.append(x)

3. Larger right-moving asteroid on top: If neither condition above is met

   • The left-moving asteroid x is destroyed by the larger right-moving asteroid
   • We don't add x to the stack (it exploded)

Finally, return the stack which contains all surviving asteroids in their final positions.

The algorithm efficiently handles all collisions in a single pass with time complexity O(n) where each asteroid is pushed and popped at most once.

Example Walkthrough

Let's walk through the example asteroids = [2, -1, 1, -2]:

Initial state: Stack is empty []

Step 1: Process asteroid 2 (right-moving)

• Since it's positive, add it directly to the stack
• Stack: [2]

Step 2: Process asteroid -1 (left-moving)

• Check for collision with top of stack (2)
• Since 2 > |-1|, asteroid -1 is destroyed
• Stack remains: [2]

Step 3: Process asteroid 1 (right-moving)

• Since it's positive, add it directly to the stack
• Stack: [2, 1]

Step 4: Process asteroid -2 (left-moving)

• Check for collision with top of stack (1)
• Since 1 < |-2|, asteroid 1 is destroyed, pop it
• Stack becomes: [2]
• Continue checking: top is now 2
• Since 2 = |-2|, both asteroids destroy each other
• Pop 2 from stack
• Stack becomes: []

Final result: [] - all asteroids have been destroyed through collisions.

Let's trace through one more example to solidify understanding: asteroids = [10, 2, -5]

Step 1: Process 10 → Stack: [10] Step 2: Process 2 → Stack: [10, 2] Step 3: Process -5

• Check collision with 2: Since 2 < |-5|, pop 2 → Stack: [10]
• Check collision with 10: Since 10 > |-5|, -5 is destroyed
• Final Stack: [10]

Result: [10]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

Each asteroid is processed at most twice - once when it's added to the stack and potentially once when it's removed during a collision. The while loop inside the for loop might seem to create O(n²) complexity, but each element can only be popped from the stack once. Therefore, across all iterations of the outer loop, the total number of operations is bounded by 2n, giving us O(n) time complexity, where n is the length of the asteroids array.

Space Complexity: O(n)

The stack stk is used to store asteroids that haven't been destroyed by collisions. In the worst case, when all asteroids are moving in the same direction (all positive or all negative), no collisions occur and all n asteroids remain in the stack. Therefore, the space complexity is O(n), where n is the length of the asteroids array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Incorrect Collision Logic Order

One of the most common mistakes is mishandling the order of collision checks after the while loop. Developers often write conditions that don't properly account for all scenarios, leading to incorrect results.

Incorrect Implementation:

# WRONG: Checking for survival before checking for mutual destruction
while stack and stack[-1] > 0 and stack[-1] < -asteroid:
    stack.pop()

# This order is problematic
if not stack or stack[-1] < 0:
    stack.append(asteroid)
elif stack and stack[-1] == -asteroid:  # This may never be reached correctly
    stack.pop()

Why it's wrong: If we check for the asteroid's survival first, we might add a left-moving asteroid to the stack even when it should have been destroyed in a mutual collision with an equal-sized right-moving asteroid.

Correct Implementation:

while stack and stack[-1] > 0 and stack[-1] < -asteroid:
    stack.pop()

# Check for mutual destruction FIRST
if stack and stack[-1] == -asteroid:
    stack.pop()
# Then check if the asteroid survives
elif not stack or stack[-1] < 0:
    stack.append(asteroid)
# Implicitly, if neither condition is met, the asteroid is destroyed

Pitfall: Off-by-One Error in Size Comparison

Another frequent error occurs when comparing asteroid sizes, forgetting that left-moving asteroids are negative.

Incorrect Implementation:

# WRONG: Comparing without considering the sign
while stack and stack[-1] > 0 and stack[-1] < asteroid:  # asteroid is negative!
    stack.pop()

Correct Implementation:

# RIGHT: Compare absolute values
while stack and stack[-1] > 0 and stack[-1] < -asteroid:  # -asteroid gives the absolute value
    stack.pop()

Pitfall: Not Handling Multiple Collisions

Some implementations fail to use a while loop for handling collisions, using an if statement instead, which only handles a single collision.

Incorrect Implementation:

# WRONG: Only handles one collision
if stack and stack[-1] > 0 and stack[-1] < -asteroid:
    stack.pop()
    # What if there's another right-moving asteroid that should also collide?

Correct Implementation:

# RIGHT: Handles all consecutive collisions
while stack and stack[-1] > 0 and stack[-1] < -asteroid:
    stack.pop()

Example demonstrating the issue:

• Input: [1, 2, 3, -5]
• With if: Would only destroy 3, incorrectly returning [1, 2, -5]
• With while: Correctly destroys 3, 2, and 1, returning [-5]