Asteroid Collision

Simulate asteroid collisions using a stack to determine the final surviving asteroids.

stack simulation arrays

Given an array `asteroids` of integers representing asteroids in a row. The absolute value of each integer represents its size, and the sign represents its direction (positive means right, negative means left). All asteroids move at the same speed. When two asteroids meet, the smaller one explodes. If they are the same size, both explode. Two asteroids moving in the same direction never meet.

Implement a function `asteroid_collision(asteroids)` that returns the state of the asteroids after all collisions. The output should preserve the order of only the surviving asteroids.

Constraints

1 <= len(asteroids) <= 10^4
-1000 <= asteroids[i] <= 1000, asteroids[i] != 0
Time: O(n)
Space: O(n)

Example

>>> asteroid_collision([5, 10, -5])
[5, 10]
>>> asteroid_collision([8, -8])
[]
>>> asteroid_collision([10, 2, -5])
[10]
>>> asteroid_collision([-2, -1, 1, 2])
[-2, -1, 1, 2]

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a stack to keep track of asteroids moving to the right that may collide with left-moving asteroids.

Only a positive asteroid followed by a negative asteroid can collide.

When a collision occurs, compare absolute values to decide which asteroid survives.

An asteroid moving left never collides with another left-moving asteroid, so it can simply be added to the result.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.