Robot Collisions

#130 Most AskedHard

Robot Collisions #130 Most Asked

Hard

Flipkart

5 views

Topics:

ArraysStacks

There are n 1-indexed robots, each having a position on a line, health, and movement direction.

You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right). All integers in positions are unique.

All robots start moving on the line simultaneously at the same speed in their given directions. If two robots ever share the same position while moving, they will collide.

If two robots collide, the robot with lower health is removed from the line, and the health of the other robot decreases by one. The surviving robot continues in the same direction it was going. If both robots have the same health, they are both removed from the line.

Your task is to determine the health of the robots that survive the collisions, in the same order that the robots were given, i.e. final health of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.

Return an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.

Note: The positions may be unsorted.

Example 1:

Input: positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
Output: [2,17,9,15,10]
Explanation: No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned, [2, 17, 9, 15, 10].

Example 2:

Input: positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"
Output: [14]
Explanation: There are 2 collisions in this example. Firstly, robot 1 and robot 2 will collide, and since both have the same health, they will be removed from the line. Next, robot 3 and robot 4 will collide and since robot 4's health is smaller, it gets removed, and robot 3's health becomes 15 - 1 = 14. Only robot 3 remains, so we return [14].

Example 3:

Input: positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL"
Output: []
Explanation: Robot 1 and robot 2 will collide and since both have the same health, they are both removed. Robot 3 and 4 will collide and since both have the same health, they are both removed. So, we return an empty array, [].

Constraints:

1 <= positions.length == healths.length == directions.length == n <= 10⁵
1 <= positions[i], healths[i] <= 10⁹
directions[i] == 'L' or directions[i] == 'R'
All values in positions are distinct

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:

What are the possible value ranges for the health and strength of each robot? Are they always positive integers?
Could the input arrays (positions, healths, strengths) be empty or null?
If two robots collide and both survive with zero health, should they both be considered destroyed and removed from the final result?
If multiple collisions occur simultaneously (e.g., robots A and B collide, and robots C and D collide at the same time), how should these collisions be processed relative to each other?
What should be returned if no robots survive the collisions? Should I return an empty list, null, or is there a specific indicator for this case?

Brute Force Solution

Approach

The brute force strategy involves simulating every possible collision between robots. We'll consider all pairs of robots and their potential interactions. This will allow us to determine which robots survive and which are destroyed.

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

Look at every possible pair of robots.
For each pair, figure out if they will collide based on their positions and directions. For example, if one is going right and another to its right is going left, they may collide.
If they will collide, determine the outcome of the collision based on their strengths. The stronger robot survives and the weaker one is destroyed. If they have equal strength, both are destroyed.
Keep track of which robots are destroyed in these collisions.
Repeat this process, considering collisions between the remaining robots.
Continue until no further collisions are possible. The robots that are still 'alive' at the end are the survivors.

Code Implementation

def robot_collisions_brute_force(positions, strengths, directions):
    number_of_robots = len(positions)
    alive_robots = list(range(number_of_robots))

    while True:
        collision_happened = False

        for i in range(len(alive_robots)):
            for j in range(i + 1, len(alive_robots)):
                robot_index_1 = alive_robots[i]
                robot_index_2 = alive_robots[j]

                position_1 = positions[robot_index_1]
                position_2 = positions[robot_index_2]

                direction_1 = directions[robot_index_1]
                direction_2 = directions[robot_index_2]

                # Only consider collisions for robots moving towards each other
                if (position_1 < position_2 and direction_1 == 1 and direction_2 == 0) or \
                   (position_1 > position_2 and direction_1 == 0 and direction_2 == 1):

                    collision_happened = True

                    strength_1 = strengths[robot_index_1]
                    strength_2 = strengths[robot_index_2]

                    # Determine the outcome of the collision
                    if strength_1 > strength_2:
                        alive_robots.remove(robot_index_2)

                        # The stronger robot wins

                    elif strength_2 > strength_1:
                        alive_robots.remove(robot_index_1)

                        # The stronger robot wins

                    else:
                        # Both robots are destroyed if they have equal strength.
                        alive_robots.remove(robot_index_1)
                        alive_robots.remove(robot_index_2)

                        # Decrement j because robot at alive_robots[j] shifted after removal
                        j -= 1

                    break # only one collision per robot per iteration

            if collision_happened:
                break # Restart the outer loop

        if not collision_happened:
            break

    # Construct the list of surviving robots.
    surviving_robots = sorted(alive_robots)
    return surviving_robots

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach considers all possible pairs of robots, leading to O(n^2) pair combinations. For each pair, determining if they will collide and resolving the collision based on strength takes constant time, O(1). However, the problem description suggests repeating this pair checking process until no further collisions are possible. In the worst-case scenario, each robot could be involved in a collision, necessitating multiple iterations of the pair checking process. Therefore, in the worst case it would be O(n) iterations. The final time complexity is O(n^2) * O(n) = O(n^3).

Space Complexity

O(N) – The brute force approach requires keeping track of which robots are destroyed. This can be implemented using a boolean array of size N, where N is the number of robots, to mark whether each robot is still alive. Additionally, the process might need to store intermediate collision results or temporary lists of surviving robots in each iteration. Therefore, the auxiliary space used scales linearly with the number of robots, resulting in O(N) space complexity.

Optimal Solution

Approach

The key to this problem is realizing that collisions only happen between robots moving in opposite directions and standing next to each other. We simulate the robots moving and colliding using a clever data structure to efficiently track the robots and their states, resolving collisions as they occur.

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

Imagine the robots standing in a line. We only care about pairs of robots that are next to each other and moving towards each other because those are the only ones that will collide.
Keep track of the robots using a structure where you can easily remove robots when they are destroyed and quickly find the next possible collision.
Go through the robots in order. If you find a pair that will collide, figure out what happens to them based on their strengths.
The weaker robot gets destroyed, and the stronger robot loses strength. If they are the same strength, both get destroyed.
Remove the destroyed robots from your data structure.
After resolving a collision, check the robots now standing next to the robot which survived the collision. They might be facing the other direction and ready to collide.
Keep doing this until no more robots are next to each other and facing opposite directions.

Code Implementation

def robot_collisions(positions, healths, directions):
    number_of_robots = len(positions)
    robots = []
    for index in range(number_of_robots):
        robots.append([positions[index], healths[index], directions[index], index])

    robots.sort()

    stack = []
    destroyed = [False] * number_of_robots

    for index in range(number_of_robots):
        current_position, current_health, current_direction, current_index = robots[index]

        # Resolve collisions with the stack until conditions are not met.
        while stack and current_direction == 'L' and stack[-1][2] == 'R':
            top_health = stack[-1][1]
            top_index = stack[-1][3]

            if current_health > top_health:
                # The robot on the stack is destroyed.
                stack.pop()
                destroyed[top_index] = True
                current_health -= 1
            elif current_health < top_health:
                # The current robot is destroyed.
                destroyed[current_index] = True
                current_health = 0
                break
            else:
                # Both robots are destroyed.
                stack.pop()
                destroyed[top_index] = True
                destroyed[current_index] = True
                current_health = 0
                break

        if current_health > 0:
            stack.append([current_position, current_health, current_direction, current_index])

    result = []
    for robot in stack:
        result.append(robot[1])

    return result

Big(O) Analysis

Time Complexity

O(n^2) – The dominant factor in the time complexity comes from the potential for each robot to be involved in multiple collision checks and resolutions. In the worst-case scenario, each robot might collide and potentially trigger a cascade of collision checks with neighboring robots. Each robot might need to be checked against all other robots to resolve potential collisions. This implies a nested loop structure where for each of the 'n' robots, we might potentially have to iterate through other robots to resolve collisions, leading to approximately n * (n-1) checks, which simplifies to O(n^2).

Space Complexity

O(N) – The primary space complexity driver is the data structure used to keep track of the robots, which can be at most the size of the initial input. Specifically, we need a data structure (like a list or stack) to store the robots and their states, from which robots are removed during collisions. In the worst case, no robots collide initially, and the data structure will hold all N robots. Therefore, the auxiliary space used scales linearly with the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty or null heights or strengths arrays	Return an empty list immediately as no collisions can occur with no robots.
Heights array and directions arrays have different lengths	Throw an exception or return an error code indicating invalid input.
Only one robot (heights array has length 1)	Return a list containing only the index of the single robot.
All robots are moving in the same direction (all 'R' or all 'L')	Return the original list of robot indices as no collisions will occur.
Two adjacent robots, one moving right, the other moving left, with very large strengths	Ensure the integer comparison doesn't overflow by using appropriate data types or modulo operations if necessary.
Heights are not unique	The algorithm should still function correctly, as height is only used for index tracking and not direct value comparison in the collision logic.
The last robot moves right and the first robot moves left (circular collision)	If using a stack, ensure it handles the case where the current robot might collide with the base of the stack even after intermediate collisions.
Large number of robots, causing memory constraints	Consider an iterative approach using an array to track survival instead of recursion to manage memory usage more efficiently.

Empty or null heights or strengths arrays

How to Handle:

Return an empty list immediately as no collisions can occur with no robots.

Heights array and directions arrays have different lengths

How to Handle:

Throw an exception or return an error code indicating invalid input.

Only one robot (heights array has length 1)

How to Handle:

Return a list containing only the index of the single robot.

All robots are moving in the same direction (all 'R' or all 'L')

How to Handle:

Return the original list of robot indices as no collisions will occur.

Two adjacent robots, one moving right, the other moving left, with very large strengths

How to Handle:

Ensure the integer comparison doesn't overflow by using appropriate data types or modulo operations if necessary.

Heights are not unique

How to Handle:

The algorithm should still function correctly, as height is only used for index tracking and not direct value comparison in the collision logic.

The last robot moves right and the first robot moves left (circular collision)

How to Handle:

If using a stack, ensure it handles the case where the current robot might collide with the base of the stack even after intermediate collisions.

Large number of robots, causing memory constraints

How to Handle:

Consider an iterative approach using an array to track survival instead of recursion to manage memory usage more efficiently.