Asteroid Collision LeetCode

Imagine yourself observing asteroids as they travel across space, occasionally crashing into one another. A minor asteroid is destroyed when it collides with a large one. However, both asteroids are destroyed in a collision when they are the same size. Your task is to write a program that simulates these collisions and tells us which asteroids are still flying after all the collisions.

Problem statement

We are given an array asteroids of integers representing asteroids. Each asteroids[i] represents the size of the asteroid at ith position along with its direction of motion (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Our goal is to the state of the asteroids after all the collisions. If two asteroids collide, the smaller one will explode. If both asteroids are equal in size, both will explode. Two asteroids moving in the same direction will never collide.

Input
- [-5, 10, -6, 20, 10, -20]
- [8, -8]
- [10, 2, -5]
Output
- [-5, 10]
- []
- [10]
Sample inputs and their outputs

Constraints:

  • 2≤2 \leq asteroids.length ≤103\leq 10^3

  • −104≤-10^4 \leq asteroids[i] ≤104\leq 10^4

  • asteroids[i] ≠0\neq 0

Example

canvasAnimation-image
1 of 3

Knowledge test

Test your knowledge of the above concept by doing the quiz below.

Choose the correct answer.

Q

Given the array asteroids = [5, -3, 2, -4, 1], which asteroids will collide?

A)

The asteroid at index 0 and index 1.

B)

The asteroid at index 1 and index 3.

C)

The asteroid at index 2 and index 4.

D)

No asteroids will collide.

Algorithm

Let's outline the approach we'll use to solve the Asteroid Collision problem:

  1. We'll create a stack to store the updated state of asteroids at each iteration of the asteroids array.

  2. We'll start iterating over the asteroids array and add the very first asteroid in this array to the stack.

  3. At each subsequent iteration of the asteroids array, we’ll compare the ith asteroid with the last asteroid stored in the stack. If the two asteroids are moving in the same direction, they will never collide. Hence, we’ll add the ith asteroid to the stack. If the two asteroids are moving toward each other, we compare their magnitudes.

    1. If the magnitudes of the colliding asteroids are unequal, the smaller asteroid will explode. If the exploding asteroid is the one in the stack, we simply pop it from the stack. However, if the exploding asteroid is the one in the asteroids array, we replace its value with 0, denoting an explosion.

    2. If the magnitudes of the colliding asteroids are equal, both will explode. We’ll pop the asteroid in the stack, and replace the asteroid in the asteroids array with 0 to denote explosion.

  4. In case of a collision, if the exploding asteroid is the one in the stack, we need to compare the asteroid in the asteroids array with the next in line asteroid in the stack. The comparison will be the same as described in step 3.

The following demonstration will help you understand the algorithm better:

We'll iterate over the asteroids array and store the updated state of the asteroids in the stack.
We'll iterate over the asteroids array and store the updated state of the asteroids in the stack.
1 of 16

From the given algorithm and the demonstration, it can be observed that the collision will only occur if:

  • The stack is not empty, and the last asteroid in the stack is moving toward the right (stack[-1] > 0)

  • The asteroid in the asteroids array is moving toward the left (asteroids[i] < 0)

Coding example

Now that we have an understanding of the algorithm, let’s code it.

def asteroidCollision(asteroids):
    stack = []
    for asteroid in asteroids:
        # Process current asteroid until no more collisions
        while stack and asteroid < 0 and stack[-1] > 0:
            if abs(stack[-1]) > abs(asteroid):
                # The current asteroid is smaller, it gets destroyed
                asteroid = 0
            elif abs(stack[-1]) < abs(asteroid):
                # The asteroid in the stack gets destroyed
                stack.pop()
            else:
                # Both asteroids are of equal size, both get destroyed
                stack.pop()
                asteroid = 0
        
        # If the current asteroid is not destroyed, add it to the stack
        if asteroid != 0:
            stack.append(asteroid)
    return stack
                    
print(asteroidCollision([-5,10,-6,20,10,-20])) # output: (-5, 10)
print(asteroidCollision([5,10,-5])) # output: [5, 10]
print(asteroidCollision([-1, 3, 2 -3])) # output: [-1, 3]

Explanation

Let’s break down the above code:

  • Line 2: We create an empty array named stack.

  • Line 3: We iterate over the asteroids array.

  • Line 4: We create a while loop to handle multiple collisions.

  • Line 5: We check if a collision will occur or not based on the conditions stated earlier.

  • Lines 8–14: We check which of the two colliding asteroids will explode, or if both will. If it is the one in the stack, we pop it. If, on the other hand, the exploding asteroid is the one in the asteroids array, we replace its value with 0. If both asteroids collide, we handle both cases.

  • Lines 15–16: If there are no more possible collisions for the given asteroid in the asteroids array, we break out of the inner loop.

  • Lines 19–20: We append the asteroid to the stack after ensuring that it did not explode (i.e., its value is not 0).

  • Line 23: We return the stack after all the possible collisions have occurred.

Time complexity

The time complexity of the provided code is O(n)O(n), where nn is the number of asteroids in the input array. This complexity stems from the loop that iterates over each asteroid in the array. Within this loop, a while loop handles multiple collisions. However, each asteroid can only be pushed onto the stack once and popped once if it explodes due to a collision. Therefore, the overall time complexity remains linear with respect to the number of asteroids.

Space complexity

The space complexity of the code is O(n)O(n), where nn is the number of asteroids in the input array. This complexity arises from the stack data structure used to store surviving asteroids after collisions. In the worst-case scenario, where no collisions occur and all asteroids survive, the stack will contain all asteroids from the input array. Other variables, such as loop control and temporary variables, have constant space requirements and do not significantly contribute to the overall space complexity. Therefore, the space complexity is determined by the size of the stack, which scales linearly with the number of asteroids.

Free Resources

Copyright ©2026 Educative, Inc. All rights reserved