#735

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Asteroid Collision

Determine the final positions of moving asteroids using a stack-based simulation for efficient collision resolution in linear time.

array stack simulation

Problem Statement

You are given an array of integers representing asteroids in a row, where the value indicates the size and the sign indicates direction: positive moves right, negative moves left. All asteroids move at the same speed along a single line, and their initial positions are given by array indices.

When two asteroids collide, the smaller one explodes; if they are the same size, both explode. Asteroids moving in the same direction never collide. Determine the final state of the asteroid row after all possible collisions.

Examples

Example 1

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

Output: [5,10]

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

Example 2

Input: asteroids = [8,-8]

Output: []

The 8 and -8 collide exploding each other.

Example 3

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

Output: [10]

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

Constraints

2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

Solution Approach

Initialize a Stack for Right-Moving Asteroids

Iterate through the asteroid array. Push all right-moving asteroids onto a stack as they represent potential future collisions. Left-moving asteroids trigger collision checks against this stack.

Resolve Collisions Iteratively

When a left-moving asteroid appears, repeatedly compare it with the top of the stack. Pop the stack if the right-moving asteroid is smaller, stop if the left-moving asteroid is destroyed, or pop both if they are equal. This ensures correct collision resolution in order.

Compile the Final Asteroid State

After processing all asteroids, combine remaining stack elements with any surviving left-moving asteroids that never collided. This produces the final stable state, reflecting all interactions accurately without rescanning the array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Each asteroid is pushed and popped at most once from the stack, giving O(n) time complexity. The stack can hold all asteroids in the worst case, resulting in O(n) space complexity, where n is the number of asteroids.

What Interviewers Usually Probe

Ask how to handle collisions without scanning the entire array repeatedly.
Probe whether the candidate correctly uses the stack to track right-moving asteroids.
Check if the candidate considers the edge case of equal-size collisions.

Common Pitfalls or Variants

Common pitfalls

Not handling multiple consecutive collisions for a single left-moving asteroid.
Confusing the order of collision resolution, leading to incorrect surviving asteroids.
Ignoring the sign and assuming all asteroids move toward each other.

Follow-up variants

Allow asteroids with varying speeds and require collision time computation.
Track positions over time and return the sequence of collisions instead of final state.
Extend to 2D grid where asteroids move in four directions and collide accordingly.

FAQ

What is the key idea behind the Asteroid Collision problem?

The core concept is using a stack to track right-moving asteroids and resolving collisions immediately when left-moving asteroids appear.

Can two asteroids moving in the same direction collide?

No, asteroids moving in the same direction never collide, so the stack only stores right-moving asteroids for collision checks.

How does the stack ensure O(n) performance?

Each asteroid is pushed and popped at most once from the stack, ensuring linear time complexity without repeated scanning.

What happens when two asteroids are the same size?

Both asteroids explode and are removed from consideration, which must be checked when popping the stack.

How should I handle consecutive collisions in this problem?

Iteratively compare the current left-moving asteroid with the stack top, popping smaller asteroids until it either explodes or no collision remains.

terminal

Solution

Solution 1: Stack

We traverse each asteroid $x$ from left to right. Since each asteroid may collide with multiple asteroids before it, we consider using a stack to store.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stk = []
        for x in asteroids:
            if x > 0:
                stk.append(x)
            else:
                while stk and stk[-1] > 0 and stk[-1] < -x:
                    stk.pop()
                if stk and stk[-1] == -x:
                    stk.pop()
                elif not stk or stk[-1] < 0:
                    stk.append(x)
        return stk

Continue Practicing

#682 baseball game #946 validate stack sequences #1441 build an array with stack operations