Watch 10 video solutions for Robot Collisions, a hard level problem involving Array, Stack, Sorting. This walkthrough by codestorywithMIK has 13,043 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= positions[i], healths[i] <= 109directions[i] == 'L' or directions[i] == 'R'positions are distinctProblem Overview: You are given robots on a number line with positions, health values, and directions (L or R). Robots moving toward each other collide. The robot with lower health is destroyed, and the winner loses one health. The task is to simulate all collisions and return the remaining health values of surviving robots in their original order.
Approach 1: Sorting and Stack-based Collision Detection (O(n log n) time, O(n) space)
Robots interact based on their positions, not their input order. The first step is to sort robot indices by position using sorting. After sorting, iterate from left to right. Maintain a stack that stores indices of robots moving to the right (R). When you encounter a robot moving left (L), it may collide with robots stored in the stack.
Resolve collisions using a loop. Compare the current robot's health with the robot on top of the stack. The robot with smaller health is removed. The survivor loses one health and may continue colliding with the next robot. If both have equal health, both are destroyed. This pattern is a classic use of a stack to simulate pairwise interactions. Each robot is pushed and popped at most once, so the collision processing itself is linear.
The overall complexity is O(n log n) due to sorting by position, while the stack simulation runs in O(n). Space complexity is O(n) for storing robot indices and survivors. This approach is the most intuitive and closely mirrors how the physical simulation works.
Approach 2: Two-Pointer Collision Simulation (O(n log n) time, O(n) space)
Another way to model the system is to first sort robots by position and then simulate interactions using two directional scans. After sorting, track right-moving robots and resolve collisions when a left-moving robot appears. Instead of an explicit stack structure, pointers track the most recent active right-moving robot that could collide with the current left-moving robot.
The algorithm repeatedly compares the current robot with the nearest opposing robot and applies the same health reduction rules used in the simulation. When a robot is destroyed, pointers advance to the next possible candidate. This technique keeps the logic iterative and avoids explicit stack operations, though conceptually it still represents the same collision frontier.
The runtime remains O(n log n) because sorting dominates the cost. The simulation step processes each robot a constant number of times, giving O(n) additional work. Space complexity is O(n) for storing sorted indices and tracking robot states.
Recommended for interviews: The sorting + stack approach is the most expected solution. It clearly models collisions and demonstrates understanding of monotonic interaction patterns similar to asteroid collision problems. Starting with a naive simulation shows understanding of the rules, but implementing the stack-based collision resolution signals strong algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Stack Collision Detection | O(n log n) | O(n) | General solution; clean collision modeling using a stack |
| Two-Pointer Collision Simulation | O(n log n) | O(n) | When implementing a pointer-based simulation without an explicit stack |