Jobs

Interviews

Discussions

Asteroid Collision

#13 Most AskedMedium

Asteroid Collision #13 Most Asked

Medium

Roku

15 views

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

Try coding it in LeetCode

Asteroid Collision

#13 Most AskedMedium

Asteroid Collision #13 Most Asked

Medium

Roku

15 views

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.

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

Try coding it in LeetCode

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:

Are there any constraints on the range of integer values for the asteroids (e.g., maximum absolute value)?
What should happen if an asteroid collides with a wall or the edge of the 'space' (if such concepts are relevant)?
If multiple asteroids collide simultaneously, how should the collisions be resolved in terms of order?
Can the input array be empty or contain only one asteroid? If so, what is the expected output?
If two asteroids of the same size collide, you mentioned both explode. Is this always the case, or could there be a scenario where one survives or something else happens?

Brute Force Solution

Approach

We have a collection of celestial rocks moving in space. Some are moving towards each other. The brute force way to figure out what happens is to consider every possible pair of rocks that could collide and see what the outcome is, then repeat this process until no more collisions can happen.

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

Look at all the rocks in their current formation.
Pick any two rocks that are moving towards each other.
Determine which rock survives the collision based on their sizes.
If one rock is destroyed, remove it from the formation.
Repeat the process of picking pairs and resolving collisions until no more rocks are moving towards each other.
If multiple collisions could happen at the same 'time', try each possible order of collisions.
Keep track of the final state of the rocks after all possible collision sequences have been explored.
Choose the final state that is consistent across all valid collision sequences.

Code Implementation

def asteroid_collision_brute_force(asteroids):
    
    while True:
        original_asteroids_count = len(asteroids)
        next_asteroids_state = list(asteroids)
        collision_occurred_in_this_pass = False

        # Iterate through all possible pairs of adjacent asteroids
        for first_asteroid_index in range(len(next_asteroids_state) - 1):
            # Check if the current pair of asteroids are moving towards each other
            if next_asteroids_state[first_asteroid_index] > 0 and next_asteroids_state[first_asteroid_index + 1] < 0:
                
                first_asteroid_size = abs(next_asteroids_state[first_asteroid_index])
                second_asteroid_size = abs(next_asteroids_state[first_asteroid_index + 1])

                if first_asteroid_size > second_asteroid_size:
                    # The second asteroid is destroyed, remove it from the list
                    next_asteroids_state.pop(first_asteroid_index + 1)
                    collision_occurred_in_this_pass = True
                    break # Restart the scan from the beginning due to list modification
                elif first_asteroid_size < second_asteroid_size:
                    # The first asteroid is destroyed, remove it from the list
                    next_asteroids_state.pop(first_asteroid_index)
                    collision_occurred_in_this_pass = True
                    break # Restart the scan from the beginning due to list modification
                else:
                    # Both asteroids are destroyed, remove both from the list
                    next_asteroids_state.pop(first_asteroid_index + 1)
                    next_asteroids_state.pop(first_asteroid_index)
                    collision_occurred_in_this_pass = True
                    break # Restart the scan from the beginning due to list modification
        
        asteroids = next_asteroids_state
        # If no collisions occurred in this entire pass, the simulation is complete
        if not collision_occurred_in_this_pass:
            break

    return asteroids

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach involves iterating through all pairs of asteroids (n*(n-1)/2) for potential collisions. For each collision, we might need to re-evaluate the entire set of remaining asteroids, and this process might repeat. If we consider that resolving a collision might trigger subsequent collisions that require rescanning, and multiple collision orders need exploration, the repeated rescanning of potentially O(n) asteroids for each of the O(n^2) initial pair checks leads to a cubic time complexity. Thus, the total operations approximate n * n * n, simplifying to O(n^3).

Space Complexity

O(n) – The most efficient approach to solve this problem involves using a stack data structure to keep track of asteroids that haven't collided yet. In the worst-case scenario, where no asteroids collide, the stack will store all N asteroids. This stack represents the auxiliary space. Therefore, the space complexity is directly proportional to the number of asteroids, N.

Optimal Solution

Approach

We can simulate the asteroid collisions by keeping track of the asteroids that are still in play. As new asteroids appear, we check if they will collide with any existing ones and resolve those collisions until no more collisions occur.

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

Imagine a holding area for asteroids that have survived previous interactions.
When a new asteroid arrives, consider its direction and size.
If the new asteroid is moving to the right, it will never collide with any asteroids already in the holding area, so just add it to the holding area.
If the new asteroid is moving to the left, it might collide with asteroids in the holding area that are moving to the right.
If the new asteroid collides with an asteroid in the holding area that is moving to the right, compare their sizes.
If the incoming asteroid is larger, the one in the holding area is destroyed, and the incoming one continues to check for further collisions with the next asteroid in the holding area.
If the asteroid in the holding area is larger or equal in size, the incoming asteroid is destroyed, and we stop checking for collisions for this incoming asteroid.
If an incoming left-moving asteroid survives all potential collisions with right-moving asteroids in the holding area, add it to the holding area.
After processing all the asteroids, the ones remaining in the holding area are the final result.

Code Implementation

def asteroid_collision(asteroids_in_motion):
    surviving_asteroids = []
    for current_asteroid in asteroids_in_motion:
        while surviving_asteroids and current_asteroid < 0 and surviving_asteroids[-1] > 0:
            # Incoming asteroid is moving left and the last surviving is moving right, potential collision.
            incoming_asteroid_size = abs(current_asteroid)
            last_surviving_asteroid_size = surviving_asteroids[-1]

            if incoming_asteroid_size > last_surviving_asteroid_size:
                # The asteroid in the holding area is destroyed, continue checking.
                surviving_asteroids.pop()
                continue
            elif incoming_asteroid_size == last_surviving_asteroid_size:
                # Both asteroids are destroyed.
                surviving_asteroids.pop()
                # Break the inner loop as the current asteroid is destroyed.
                break
            else:
                # The incoming asteroid is destroyed.
                # Break the inner loop as the current asteroid is destroyed.
                break
        else:
            # This 'else' belongs to the 'while' loop.
            # If the inner loop completed without a 'break', it means the current asteroid survived.
            # This happens if the surviving_asteroids list is empty, or if the current asteroid is moving right,
            # or if the last surviving asteroid is also moving left.
            surviving_asteroids.append(current_asteroid)

    return surviving_asteroids

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array of n asteroids once. For each asteroid, it might perform a series of 'while' loop checks against asteroids in a holding area (simulated by a stack). However, each asteroid is added to the holding area at most once and removed from it at most once due to collisions. Therefore, the total number of operations, considering both the outer loop and the inner 'while' loop checks, is proportional to the number of asteroids, n, leading to a linear time complexity.

Space Complexity

O(n) – The primary auxiliary data structure used is a holding area, which functions like a stack, to keep track of surviving asteroids. In the worst-case scenario, all asteroids might survive and be pushed onto this holding area. If N is the total number of asteroids in the input array, the holding area can grow to a maximum size proportional to N. Therefore, the auxiliary space complexity is O(n).

Edge Cases

Case	How to Handle
Empty input array	An empty input array should result in an empty output array.
Input array with a single asteroid	An input array with one asteroid should return that single asteroid as the result.
All asteroids moving in the same direction (all positive or all negative)	No collisions will occur, and the original array should be returned.
Asteroids of equal size colliding	Both asteroids should explode and be removed from the simulation.
A right-moving asteroid followed by a smaller left-moving asteroid	The smaller left-moving asteroid should explode, and the right-moving asteroid should continue.
A left-moving asteroid followed by a smaller right-moving asteroid	No collision will occur as they are moving away from each other.
A large right-moving asteroid followed by a smaller left-moving asteroid	The smaller left-moving asteroid explodes, and the larger right-moving asteroid continues unaffected.
A large left-moving asteroid followed by a smaller right-moving asteroid	No collision will occur as they are moving away from each other.

Empty input array

How to Handle:

An empty input array should result in an empty output array.

Input array with a single asteroid

How to Handle:

An input array with one asteroid should return that single asteroid as the result.

All asteroids moving in the same direction (all positive or all negative)

How to Handle:

No collisions will occur, and the original array should be returned.

Asteroids of equal size colliding

How to Handle:

Both asteroids should explode and be removed from the simulation.

A right-moving asteroid followed by a smaller left-moving asteroid

How to Handle:

The smaller left-moving asteroid should explode, and the right-moving asteroid should continue.

A left-moving asteroid followed by a smaller right-moving asteroid

How to Handle:

No collision will occur as they are moving away from each other.

A large right-moving asteroid followed by a smaller left-moving asteroid

How to Handle:

The smaller left-moving asteroid explodes, and the larger right-moving asteroid continues unaffected.

A large left-moving asteroid followed by a smaller right-moving asteroid

How to Handle:

No collision will occur as they are moving away from each other.

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:

Are there any constraints on the range of integer values for the asteroids (e.g., maximum absolute value)?
What should happen if an asteroid collides with a wall or the edge of the 'space' (if such concepts are relevant)?
If multiple asteroids collide simultaneously, how should the collisions be resolved in terms of order?
Can the input array be empty or contain only one asteroid? If so, what is the expected output?
If two asteroids of the same size collide, you mentioned both explode. Is this always the case, or could there be a scenario where one survives or something else happens?

Brute Force Solution

Approach

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

Look at all the rocks in their current formation.
Pick any two rocks that are moving towards each other.
Determine which rock survives the collision based on their sizes.
If one rock is destroyed, remove it from the formation.
Repeat the process of picking pairs and resolving collisions until no more rocks are moving towards each other.
If multiple collisions could happen at the same 'time', try each possible order of collisions.
Keep track of the final state of the rocks after all possible collision sequences have been explored.
Choose the final state that is consistent across all valid collision sequences.

Code Implementation

def asteroid_collision_brute_force(asteroids):
    
    while True:
        original_asteroids_count = len(asteroids)
        next_asteroids_state = list(asteroids)
        collision_occurred_in_this_pass = False

        # Iterate through all possible pairs of adjacent asteroids
        for first_asteroid_index in range(len(next_asteroids_state) - 1):
            # Check if the current pair of asteroids are moving towards each other
            if next_asteroids_state[first_asteroid_index] > 0 and next_asteroids_state[first_asteroid_index + 1] < 0:
                
                first_asteroid_size = abs(next_asteroids_state[first_asteroid_index])
                second_asteroid_size = abs(next_asteroids_state[first_asteroid_index + 1])

                if first_asteroid_size > second_asteroid_size:
                    # The second asteroid is destroyed, remove it from the list
                    next_asteroids_state.pop(first_asteroid_index + 1)
                    collision_occurred_in_this_pass = True
                    break # Restart the scan from the beginning due to list modification
                elif first_asteroid_size < second_asteroid_size:
                    # The first asteroid is destroyed, remove it from the list
                    next_asteroids_state.pop(first_asteroid_index)
                    collision_occurred_in_this_pass = True
                    break # Restart the scan from the beginning due to list modification
                else:
                    # Both asteroids are destroyed, remove both from the list
                    next_asteroids_state.pop(first_asteroid_index + 1)
                    next_asteroids_state.pop(first_asteroid_index)
                    collision_occurred_in_this_pass = True
                    break # Restart the scan from the beginning due to list modification
        
        asteroids = next_asteroids_state
        # If no collisions occurred in this entire pass, the simulation is complete
        if not collision_occurred_in_this_pass:
            break

    return asteroids

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine a holding area for asteroids that have survived previous interactions.
When a new asteroid arrives, consider its direction and size.
If the new asteroid is moving to the right, it will never collide with any asteroids already in the holding area, so just add it to the holding area.
If the new asteroid is moving to the left, it might collide with asteroids in the holding area that are moving to the right.
If the new asteroid collides with an asteroid in the holding area that is moving to the right, compare their sizes.
If the incoming asteroid is larger, the one in the holding area is destroyed, and the incoming one continues to check for further collisions with the next asteroid in the holding area.
If the asteroid in the holding area is larger or equal in size, the incoming asteroid is destroyed, and we stop checking for collisions for this incoming asteroid.
If an incoming left-moving asteroid survives all potential collisions with right-moving asteroids in the holding area, add it to the holding area.
After processing all the asteroids, the ones remaining in the holding area are the final result.

Code Implementation

def asteroid_collision(asteroids_in_motion):
    surviving_asteroids = []
    for current_asteroid in asteroids_in_motion:
        while surviving_asteroids and current_asteroid < 0 and surviving_asteroids[-1] > 0:
            # Incoming asteroid is moving left and the last surviving is moving right, potential collision.
            incoming_asteroid_size = abs(current_asteroid)
            last_surviving_asteroid_size = surviving_asteroids[-1]

            if incoming_asteroid_size > last_surviving_asteroid_size:
                # The asteroid in the holding area is destroyed, continue checking.
                surviving_asteroids.pop()
                continue
            elif incoming_asteroid_size == last_surviving_asteroid_size:
                # Both asteroids are destroyed.
                surviving_asteroids.pop()
                # Break the inner loop as the current asteroid is destroyed.
                break
            else:
                # The incoming asteroid is destroyed.
                # Break the inner loop as the current asteroid is destroyed.
                break
        else:
            # This 'else' belongs to the 'while' loop.
            # If the inner loop completed without a 'break', it means the current asteroid survived.
            # This happens if the surviving_asteroids list is empty, or if the current asteroid is moving right,
            # or if the last surviving asteroid is also moving left.
            surviving_asteroids.append(current_asteroid)

    return surviving_asteroids

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	An empty input array should result in an empty output array.
Input array with a single asteroid	An input array with one asteroid should return that single asteroid as the result.
All asteroids moving in the same direction (all positive or all negative)	No collisions will occur, and the original array should be returned.
Asteroids of equal size colliding	Both asteroids should explode and be removed from the simulation.
A right-moving asteroid followed by a smaller left-moving asteroid	The smaller left-moving asteroid should explode, and the right-moving asteroid should continue.
A left-moving asteroid followed by a smaller right-moving asteroid	No collision will occur as they are moving away from each other.
A large right-moving asteroid followed by a smaller left-moving asteroid	The smaller left-moving asteroid explodes, and the larger right-moving asteroid continues unaffected.
A large left-moving asteroid followed by a smaller right-moving asteroid	No collision will occur as they are moving away from each other.

Empty input array

How to Handle:

An empty input array should result in an empty output array.

Input array with a single asteroid

How to Handle:

An input array with one asteroid should return that single asteroid as the result.

All asteroids moving in the same direction (all positive or all negative)

How to Handle:

No collisions will occur, and the original array should be returned.

Asteroids of equal size colliding

How to Handle:

Both asteroids should explode and be removed from the simulation.

A right-moving asteroid followed by a smaller left-moving asteroid

How to Handle:

The smaller left-moving asteroid should explode, and the right-moving asteroid should continue.

A left-moving asteroid followed by a smaller right-moving asteroid

How to Handle:

No collision will occur as they are moving away from each other.

A large right-moving asteroid followed by a smaller left-moving asteroid

How to Handle:

The smaller left-moving asteroid explodes, and the larger right-moving asteroid continues unaffected.

A large left-moving asteroid followed by a smaller right-moving asteroid

How to Handle:

No collision will occur as they are moving away from each other.

0/16 Roku questions completed

0/16 completed