Asteroid Collision

Medium

Apple

7 views

Topics:

ArraysStacks

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteroid in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

For example:

asteroids = [5,10,-5] should return [5,10] because the 10 and -5 collide resulting in 10. Then the 5 and 10 will never collide.
asteroids = [8,-8] should return [] because the 8 and -8 collide exploding each other.
asteroids = [10,2,-5] should return [10] because the 2 and -5 collide resulting in -5. Then the 10 and -5 collide resulting in 10.

Write an algorithm to efficiently determine the final state of the asteroids after all collisions, considering the constraints: 2 <= asteroids.length <= 10^4, -1000 <= asteroids[i] <= 1000, and asteroids[i] != 0.

Asteroid Collision

Medium

Apple

7 views

Topics:

ArraysStacks

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteroid in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

For example:

asteroids = [5,10,-5] should return [5,10] because the 10 and -5 collide resulting in 10. Then the 5 and 10 will never collide.
asteroids = [8,-8] should return [] because the 8 and -8 collide exploding each other.
asteroids = [10,2,-5] should return [10] because the 2 and -5 collide resulting in -5. Then the 10 and -5 collide resulting in 10.

Write an algorithm to efficiently determine the final state of the asteroids after all collisions, considering the constraints: 2 <= asteroids.length <= 10^4, -1000 <= asteroids[i] <= 1000, and asteroids[i] != 0.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `asteroids` array?
Can the input array be empty or null? If so, what should I return?
If multiple collisions occur simultaneously, what is the order in which they should be resolved?
If all asteroids explode, should I return an empty array or null?
Can the input array contain zero values, and if so, how should they be treated?

Brute Force Solution

Approach

The brute force method for asteroid collisions is like watching each asteroid crash individually and seeing what's left. We simulate the collisions step-by-step, removing asteroids as they explode until we find the final stable state.

Here's how the algorithm would work step-by-step:

Start with the first asteroid in the sequence.
Check if it will collide with the asteroid immediately to its right. Remember that asteroids moving in the same direction don't collide.
If they collide, figure out which one (if any) survives based on their sizes. The smaller one is removed, and if they are the same size, both are removed.
Repeat the collision check and removal process for adjacent asteroids until there are no more collisions happening between immediate neighbors.
Move on to the next asteroid that hasn't been involved in a collision yet and repeat the same process.
Continue this process for all the asteroids, one by one, until no more collisions are possible.
The asteroids that remain are the final result.

Code Implementation

def asteroid_collision_brute_force(asteroids): 
    list_of_asteroids = asteroids[:] 
    collisions_happened = True

    while collisions_happened:
        collisions_happened = False
        index = 0
        while index < len(list_of_asteroids) - 1:
            first_asteroid = list_of_asteroids[index]
            second_asteroid = list_of_asteroids[index + 1]

            # Asteroids must be moving in opposite directions to collide
            if first_asteroid > 0 and second_asteroid < 0:
                collisions_happened = True

                if abs(first_asteroid) > abs(second_asteroid):
                    # Second asteroid destroyed
                    del list_of_asteroids[index + 1]

                elif abs(first_asteroid) < abs(second_asteroid):
                    # First asteroid destroyed
                    del list_of_asteroids[index]
                    
                else:
                    # Both asteroids destroyed
                    del list_of_asteroids[index:index + 2]
                    
                # Reset the index to start from the beginning
                index = 0
                continue
            
            index += 1

    return list_of_asteroids

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each asteroid in the input array of size n. The inner loop repeatedly checks for collisions between adjacent asteroids and potentially removes elements, potentially shifting the remaining asteroids. In the worst case, each asteroid might collide and cause shifts multiple times, resulting in checking nearly all other elements for each element. Thus, the total number of operations is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach repeatedly checks and resolves collisions between adjacent asteroids. The resulting surviving asteroids are implicitly stored in place as the algorithm progresses by removing elements. However, the repeated removals can be conceptually viewed as building a new list of survivors. In the worst-case scenario, where asteroids are repeatedly colliding and being removed, a significant portion of the original asteroids array may need to be virtually copied or tracked to determine the final state. This process can require maintaining a collection whose size is related to the original input size, N, hence resulting in O(N) space complexity. The space is used to store the intermediate state of the asteroid list.

Optimal Solution

Approach

The key to solving this problem efficiently is to simulate the collisions using a stack. We'll go through each asteroid one by one, and use the stack to keep track of the asteroids that haven't exploded yet. The stack helps us easily resolve collisions between asteroids moving in opposite directions.

Here's how the algorithm would work step-by-step:

Imagine you have a stack to keep track of asteroids that are still around after collisions.
Look at each asteroid in the given order.
If the current asteroid is moving to the right, just put it on the stack because it won't collide with anything yet.
If the current asteroid is moving to the left, check the asteroids already on the stack to see if there will be a collision.
If the top asteroid on the stack is moving to the right (opposite direction), then they might collide. If the left moving asteroid is bigger than the right moving asteroid on the stack, the right moving asteroid explodes and you continue to check the next asteroid in the stack for a collision.
If the right moving asteroid on the stack is bigger, the left moving asteroid explodes and you're done with the current asteroid. Move on to the next asteroid in the list.
If they are the same size, both asteroids explode, and you move on to the next asteroid.
If the top asteroid on the stack is moving to the left (same direction), they will not collide, add the current asteroid to the stack.
After looking at all the asteroids, what's left on the stack is your final list of asteroids that didn't explode.

Code Implementation

def asteroidCollision(asteroids):
    asteroid_stack = []

    for current_asteroid in asteroids:
        # Process each asteroid to determine final state
        while asteroid_stack and current_asteroid < 0 and asteroid_stack[-1] > 0:
            # Handle collision between asteroids going in opposite directions.
            top_asteroid = asteroid_stack[-1]

            if abs(current_asteroid) > top_asteroid:
                asteroid_stack.pop()
                continue # Continue collision checks with next asteroid in stack
            elif abs(current_asteroid) == top_asteroid:
                asteroid_stack.pop()
                break # Both asteroids explode
            else:
                break # Current asteroid explodes

        else:
            # If the 'while' loop completes without 'break',
            asteroid_stack.append(current_asteroid)

    return asteroid_stack

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input array of n asteroids once. Inside the loop, we potentially perform operations on the stack. The critical observation is that each asteroid is added to the stack at most once and removed from the stack at most once. Therefore, the total number of stack operations across all iterations of the main loop is also bounded by a constant factor of n. Thus, the overall time complexity is O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from the stack which is used to store asteroids that have not yet exploded. In the worst-case scenario, all asteroids could be moving to the right, resulting in all N asteroids being added to the stack. Therefore, the auxiliary space used by the stack grows linearly with the input size N. Thus the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array immediately as there are no asteroids to collide.
Single element input array	Return the array directly as there are no collisions possible.
All asteroids moving in the same direction (all positive or all negative)	No collisions will occur, so return the input array unchanged.
Large asteroids crashing into small asteroids	The small asteroids should be destroyed and the larger ones should continue until another collision.
Asteroids of equal size colliding	Both asteroids should be destroyed (removed from the resulting array).
A sequence of collisions where multiple asteroids are destroyed in a chain reaction	Use a stack to efficiently track the remaining asteroids and handle consecutive collisions.
Integer overflow if asteroid sizes are very large.	Use a data type that can accommodate larger numbers, like long, to prevent overflow.
Alternating positive and negative asteroids leading to many potential collisions.	Stack will effectively simulate collisions in the correct order ensuring correct result.