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 i^th 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.

Algorithm

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

We'll create a stack to store the updated state of asteroids at each iteration of the asteroids array.
We'll start iterating over the asteroids array and add the very first asteroid in this array to the stack.
At each subsequent iteration of the asteroids array, we’ll compare the i^th 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 i^thasteroid 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.
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:

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)$ , where $n$ 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)$ , where $n$ 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 AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Asteroid Collision LeetCode

Problem statement

Example

Knowledge test

Algorithm

Coding example

Explanation

Time complexity

Space complexity