LeetCode 2751 - Robot Collisions
This problem describes a simulation of robots moving on a one-dimensional line, each with a given starting position, health, and direction. Every robot moves at the same speed, and collisions occur when two robots meet at the same position.
Difficulty: 🔴 Hard
Topics: Array, Stack, Sorting, Simulation
Solution
Problem Understanding
This problem describes a simulation of robots moving on a one-dimensional line, each with a given starting position, health, and direction. Every robot moves at the same speed, and collisions occur when two robots meet at the same position. The key rules are: if two robots collide, the one with lower health is removed, the one with higher health loses one health point and continues in the same direction, and if both have the same health, both are removed.
The input consists of three arrays: positions, healths, and directions. Positions are unique but may be unsorted. The output is an array of remaining robots’ health values in the original input order. The problem constraints allow up to 100,000 robots with large integer positions and healths, so a naive simulation that checks every pair of robots over time would be computationally infeasible.
Important edge cases include robots all moving in the same direction (no collisions), multiple sequential collisions, and collisions where healths are equal, which results in removal of both robots.
Approaches
Brute Force
The brute-force approach simulates every timestep: move each robot by one unit in its direction and check for collisions. When two robots occupy the same position, we resolve the collision based on health rules. Continue until no more collisions occur. This approach is correct but inefficient because it has O(n²) complexity for collision detection in the worst case. With n up to 10^5, this is far too slow.
Optimal Approach
A key observation is that collisions only occur between a right-moving robot and a left-moving robot, since robots moving in the same direction never meet. Therefore, we can simulate collisions using a stack to store the indices of right-moving robots. When encountering a left-moving robot, we compare it with the top of the stack (the last right-moving robot) and resolve collisions iteratively until either the stack is empty or the left-moving robot is destroyed. This efficiently handles all collisions in a single pass after sorting robots by position.
The optimal approach consists of the following ideas:
- Pair each robot's position with its index, health, and direction.
- Sort robots by position so collisions can be simulated in order.
- Use a stack to track right-moving robots; resolve collisions with left-moving robots.
- Store the surviving health in a results array at the original indices.
This approach achieves O(n log n) time due to sorting and O(n) space for the stack and results array.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Simulates each timestep, too slow for large n |
| Optimal | O(n log n) | O(n) | Uses sorting and a stack to resolve collisions efficiently |
Algorithm Walkthrough
-
Pair each robot's position with its index, health, and direction.
-
Sort the robots by position in ascending order to simulate collisions in physical order along the line.
-
Initialize a stack to store the indices of right-moving robots.
-
Initialize a results array with original health values; surviving robots will retain or reduce their health here.
-
Iterate through the sorted robots:
-
If the robot is moving right, push its index onto the stack.
-
If the robot is moving left, repeatedly check the top of the stack (last right-moving robot) and resolve collisions:
-
If the right-moving robot’s health is greater than the left-moving robot, decrement the right-moving robot's health by one, mark the left-moving robot as destroyed, and stop.
-
If the left-moving robot’s health is greater, decrement the left-moving robot's health by one, pop the right-moving robot from the stack, and continue.
-
If their healths are equal, mark both robots as destroyed and pop the right-moving robot from the stack.
-
After iterating through all robots, the results array contains the surviving healths in the original order. Filter out destroyed robots.
-
Return the surviving health values.
Why it works: The invariant is that the stack always contains unresolved right-moving robots that may collide with future left-moving robots. By processing in position order and resolving collisions with the top of the stack, all interactions are handled correctly, and robots moving in the same direction never need to collide.
Python Solution
from typing import List
class Solution:
def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
n = len(positions)
robots = sorted([(pos, i, healths[i], directions[i]) for i, pos in enumerate(positions)])
stack = []
alive = [True] * n
res = healths[:]
for pos, idx, health, dirc in robots:
if dirc == 'R':
stack.append(idx)
else:
while stack and res[idx] > 0:
top_idx = stack[-1]
if res[top_idx] > res[idx]:
res[top_idx] -= 1
alive[idx] = False
break
elif res[top_idx] < res[idx]:
res[idx] -= 1
alive[top_idx] = False
stack.pop()
else:
alive[idx] = False
alive[top_idx] = False
stack.pop()
break
return [res[i] for i in range(n) if alive[i]]
Explanation: We sort robots by position, then use a stack for right-moving robots. Left-moving robots resolve collisions with the stack's top element until they are destroyed or the stack is empty. The alive array tracks survivors, and res stores updated healths.
Go Solution
func survivedRobotsHealths(positions []int, healths []int, directions string) []int {
type Robot struct {
pos, idx, health int
dir byte
}
n := len(positions)
robots := make([]Robot, n)
for i := 0; i < n; i++ {
robots[i] = Robot{positions[i], i, healths[i], directions[i]}
}
sort.Slice(robots, func(i, j int) bool { return robots[i].pos < robots[j].pos })
stack := []int{}
alive := make([]bool, n)
for i := 0; i < n; i++ { alive[i] = true }
res := make([]int, n)
copy(res, healths)
for _, r := range robots {
if r.dir == 'R' {
stack = append(stack, r.idx)
} else {
idx := r.idx
for len(stack) > 0 && res[idx] > 0 {
topIdx := stack[len(stack)-1]
if res[topIdx] > res[idx] {
res[topIdx] -= 1
alive[idx] = false
break
} else if res[topIdx] < res[idx] {
res[idx] -= 1
alive[topIdx] = false
stack = stack[:len(stack)-1]
} else {
alive[idx] = false
alive[topIdx] = false
stack = stack[:len(stack)-1]
break
}
}
}
}
ans := []int{}
for i := 0; i < n; i++ {
if alive[i] {
ans = append(ans, res[i])
}
}
return ans
}
Go-specific notes: We use slices for the stack and results, handle byte vs string for directions, and use sort.Slice to sort robots by position. Indexing differences in slices are carefully managed.
Worked Examples
Example 1: positions=[5,4,3,2,1], healths=[2,17,9,15,10], directions="RRRRR"
Sorted by position: [(1,4,10,'R'), (2,3,15,'R'), (3,2,9,'R'), (4,1,17,'R'), (5,0,2,'R')]
All robots move right; stack accumulates indices [4,3,2,1,0]. No left-moving robot to collide. Result: [2,17,9,15,10].
Example 2: positions=[3,5,2,6], healths=[10,10,15,12], directions="RLRL"
Sorted by position: [(2,2,15,'R'), (3,0,10,'R'), (5,1,10,'L'), (6,3,12,'L')]
First collision: index 0 vs index 1 (both 10), both removed. Stack has index 2. Next collision: index 2 vs index 3, 15 vs 12 → index 2 health 14, index 3 removed. Result: [14].
Example 3: positions=[1,2,5,6], healths=[10,10,11,11], directions="RLRL"
Sorted by position: [(1,0,10,'R'), (2,1,10,'L'), (5,2,11,'R'), (6,3,11,'L')]
Collision 0 vs 1 → both removed. Collision 2 vs 3 → both removed. Result: [].
Complexity Analysis
| Measure