How do you solve Robot Collisions on LeetCode?

Robot Collisions (LeetCode #2751) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Robots moving in the same direction will not collide.

What is the time complexity of Robot Collisions?

The optimal solution for Robot Collisions runs in O(n log n) time and uses O(n) space. Sorting the robots takes O(n log n), and processing them with a stack takes O(n), leading to an overall complexity of O(n log n).

What is the brute force solution for Robot Collisions?

The brute force approach for Robot Collisions is Brute Force, with O(n²) time complexity and O(1) space complexity. We can simulate each robot's movement and check for collisions at every time step. This approach is straightforward but inefficient as it checks every possible pair of robots. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Robot Collisions?

Robot Collisions uses the following concepts: Array, Stack, Sorting, Simulation. The recommended patterns to study are: Stack, Sorting.

What are the interview tips for Robot Collisions?

Think about how to efficiently track surviving robots. Use data structures like stacks to simplify collision handling. Always clarify the problem constraints and edge cases with the interviewer.

What are common mistakes when solving Robot Collisions?

Not considering the order of processing robots based on their positions. Failing to handle edge cases where all robots have the same health.

#2751

Robot Collisions

Hard

ArrayStackSortingSimulationStackSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

By using a stack, we can efficiently track surviving robots and handle collisions as they occur, processing robots based on their positions.

⚙️

Algorithm

3 steps

1Step 1: Pair positions with their healths and sort them based on positions.
2Step 2: Use a stack to keep track of surviving robots as we iterate through the sorted robots.
3Step 3: For each robot, check the direction: if it's moving right, push it onto the stack. If it's moving left, check for collisions with the robot on top of the stack.

solution.py21 lines

1def robotCollisions(positions, healths, directions):
2    robots = sorted(zip(positions, healths, directions))
3    stack = []
4    for pos, health, dir in robots:
5        if dir == 'R':
6            stack.append([health])
7        else:
8            while stack and stack[-1][0] > 0:
9                top_health = stack[-1][0]
10                if top_health > health:
11                    stack[-1][0] -= 1
12                    break
13                elif top_health < health:
14                    stack.pop()
15                    health -= 1
16                else:
17                    stack.pop()
18                    health = 0
19            if health > 0:
20                stack.append([health])
21    return [health[0] for health in stack if health[0] > 0]

ℹ

Complexity note: Sorting the robots takes O(n log n), and processing them with a stack takes O(n), leading to an overall complexity of O(n log n).

1Robots moving in the same direction will not collide.
2Collisions only occur when a robot moving left meets a robot moving right.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.