Asteroid Collision

Medium

Nuro

1 view

Topics:

ArraysStacks

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod 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.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

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

Asteroid Collision

Medium

Nuro

1 view

Topics:

ArraysStacks

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod 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.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
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 possible values for the integers representing the asteroids' sizes?
Can the input array be empty or null? If so, what should I return?
If multiple collisions occur sequentially, how should I resolve them? For example, if A collides with B, and then the result collides with C, do I resolve A-B first, then the result with C?
If two asteroids of the same size collide, and they both explode, how should the resulting array be structured?
Is the order of the remaining asteroids in the output important? Should it match the original order?

Brute Force Solution

Approach

Imagine you have a series of asteroids moving in different directions and sizes. The brute force method essentially simulates every single collision that could possibly occur, one at a time, until no more collisions are possible. It's like watching the asteroids crash over and over until things settle down.

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

Start by looking at the first two asteroids.
If they are moving in opposite directions and will collide, compare their sizes.
If one asteroid is bigger, the smaller one is destroyed and removed from the group. If they are the same size, both are destroyed.
If they are moving in the same direction, or moving away from each other, they won't collide, so move on to the next pair of asteroids.
Keep doing this, comparing pairs of asteroids one by one, from beginning to end, resolving any collisions you find.
Repeat this entire process from the beginning again. This is because resolving one collision might create new collision opportunities down the line.
Continue repeating the whole process until you can go through the entire group of asteroids without finding any new collisions. At that point, the remaining asteroids are the ones that survive.

Code Implementation

def asteroid_collision_brute_force(asteroids):    collisions_happened = True
    while collisions_happened:
        collisions_happened = False
        index = 0
        while index < len(asteroids) - 1:
            first_asteroid = asteroids[index]
            second_asteroid = asteroids[index + 1]

            # Check if asteroids are moving in opposite directions
            if first_asteroid > 0 and second_asteroid < 0:
                collisions_happened = True

                # Determine which asteroid survives based on size
                if abs(first_asteroid) > abs(second_asteroid):
                    asteroids.pop(index + 1)

                elif abs(first_asteroid) < abs(second_asteroid):
                    asteroids.pop(index)

                # If equal size, remove both asteroids
                else:
                    asteroids.pop(index + 1)
                    asteroids.pop(index)

            else:
                index += 1

    return asteroids

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The outer loop iterates until no collisions occur in a single pass. In the worst case, a collision might only resolve one asteroid per pass, potentially requiring n passes through the asteroid list. The inner loop iterates through the n asteroids, comparing adjacent pairs to detect collisions. Resolving a collision within the inner loop involves potentially modifying the array which takes O(n) time in the worst case where the collision occurs early in the list and elements must be shifted. Therefore, the overall time complexity is O(n * n * n) = O(n³).

Space Complexity

O(1) – The provided brute force approach operates primarily in-place. While the algorithm modifies the input array, it doesn't allocate significant extra space dependent on the input size N (where N is the number of asteroids). There is no indication of auxiliary data structures like temporary lists, hash maps, or recursion contributing to space complexity. Therefore, the auxiliary space used is constant, independent of the number of asteroids.

Optimal Solution

Approach

We want to simulate asteroids colliding in space. The core idea is to use a stack to keep track of the asteroids that haven't exploded yet. If a new asteroid collides with the previous one, we resolve the collision and decide which asteroids remain, if any.

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

Imagine a stack of asteroids that haven't crashed yet.
Start with the first asteroid and add it to the stack.
Consider the next asteroid: If it's heading to the right and the last asteroid in the stack is heading to the left, they might crash.
If a crash is possible, check which asteroid is bigger. The smaller one explodes. If they're the same size, both explode.
Keep resolving crashes until the new asteroid doesn't crash into the last one in the stack, or the stack is empty.
If the new asteroid survives all crashes, add it to the stack.
Repeat for all asteroids. At the end, the stack contains the asteroids that are still floating around.

Code Implementation

def asteroid_collision(asteroids):
    asteroid_stack = []

    for new_asteroid in asteroids:
        while asteroid_stack and new_asteroid < 0 and asteroid_stack[-1] > 0:
            # Resolve potential collision
            top_asteroid = asteroid_stack[-1]

            if top_asteroid < abs(new_asteroid):
                asteroid_stack.pop()
            elif top_asteroid == abs(new_asteroid):
                asteroid_stack.pop()
                new_asteroid = 0 #Asteroid destroyed
                break # Break inner while loop because asteroid is destroyed
            else:
                new_asteroid = 0 #Asteroid destroyed
                break # Break inner while loop because asteroid is destroyed

        # Only push if it survives collisions
        if new_asteroid:
            asteroid_stack.append(new_asteroid)

    return asteroid_stack

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

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

Space Complexity

O(N) – The algorithm uses a stack to store the asteroids that haven't exploded. In the worst-case scenario, no asteroids collide, and all N asteroids are added to the stack. Therefore, the auxiliary space used by the stack grows linearly with the number of asteroids. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty or null input array	Return an empty array if the input is null or has zero length.
Input array with only one element	Return the input array itself as there are no collisions possible.
All asteroids moving in the same direction (all positive or all negative)	The stack will simply accumulate all asteroids and the final result is the original array.
Large input array causing potential memory issues	The stack-based approach has O(n) space complexity, so ensure sufficient memory allocation for very large arrays.
Integer overflow if asteroid sizes are very large and the collision comparison is not careful.	Use appropriate data types (e.g., long) to prevent potential integer overflow during comparisons.
A series of collisions that eventually results in an empty stack.	The stack should be handled correctly, and the function should return an empty array at the end.
Alternating positive and negative asteroids of increasing size that all collide.	The stack operations of adding and removing elements must be handled carefully to ensure the correct final state.
An asteroid moving left collides with a larger series of asteroids all moving right.	The algorithm needs to continuously compare with asteroids in the stack until the left moving asteroid is destroyed, or the stack is empty, or the left moving asteroid is larger than the top of the stack.