LeetCode Solutions Blog

Robot Collisions

Number: 2846

Difficulty: Hard

Paid? No

Problem Description

We are given n robots each with a unique position on a line, a health value, and a movement direction (left or right). All robots start moving simultaneously at the same speed. When two robots meet, a collision occurs: the robot with the lower health is removed and the surviving robot loses 1 health. If both have equal health, both are removed. The task is to compute the final healths of the surviving robots and return them in the input order.

Key Insights

Collisions occur only when a robot moving right encounters a robot moving left.
Sorting the robots by their positions makes it easier to simulate interactions among approaching robots.
A stack can be used to keep track of right-moving robots that might collide with a left-moving robot.
When processing a left-moving robot, it may encounter multiple right-moving robots (from the stack) undergoing sequential collisions.
The final answer must be reported in the original input order, so tracking the original indices is necessary.

Space and Time Complexity

Time Complexity: O(n), since each robot is processed at most once. Space Complexity: O(n), for storing robot records and the auxiliary stack.

Solution

We first combine each robot's information (position, health, direction, and original index) into a single record and sort these records by position. We then iterate over these sorted records. If the robot is moving right, we push it onto a stack. When a left-moving robot is encountered, we simulate collisions with robots in the right-moving stack:

While the stack is not empty and the left-moving robot still survives (health > 0), we compare its health with the health of the robot on top of the stack.
If the left-moving robot’s health is greater, it eliminates the right-moving robot (loses 1 health) and we pop from the stack.
If both robots have equal health, both are removed.
If the right-moving robot’s health is greater, it loses 1 health and the left-moving robot is removed. Robots that survive (either left-moving ones that finish collisions or right-moving ones remaining in the stack) are recorded. Finally, we assemble the surviving robots’ health values according to their original order.

Code Solutions

# Python solution with line-by-line comments
from typing import List

def robotCollisions(positions: List[int], healths: List[int], directions: str) -> List[int]:
    # Define a robot record as (position, health, direction, original_index)
    robots = [(pos, health, directions[i], i) for i, (pos, health) in enumerate(zip(positions, healths))]
    # Sort the robots by position
    robots.sort(key=lambda x: x[0])
    
    # This stack will store right-moving robots that haven't collided yet.
    right_stack = []
    # This list will record survivors which are left-moving robots that passed all collisions.
    survivors = []
    
    # Process each robot in sorted order
    for pos, health, direction, idx in robots:
        if direction == 'R':
            # For a right-moving robot, push onto the right_stack.
            right_stack.append([health, idx])
        else:  # direction == 'L'
            current_health = health
            # Process collisions with the right-moving robots in the stack.
            while right_stack and current_health > 0:
                # Get health of the robot from the right_stack (last inserted)
                right_health, right_idx = right_stack[-1]
                if right_health < current_health:
                    # Left-moving robot wins this collision:
                    # Remove the right-moving robot and reduce current health by 1.
                    right_stack.pop()
                    current_health -= 1
                elif right_health == current_health:
                    # Both robots get removed.
                    right_stack.pop()
                    current_health = 0  # this left-moving robot also gets removed.
                else:  # right_health > current_health
                    # The right-moving robot wins: reduce its health by 1 and the left robot is removed.
                    right_stack[-1][0] -= 1
                    current_health = 0
            # If the left-moving robot survived (no more collisions), record it.
            if current_health > 0:
                survivors.append((idx, current_health))
    
    # Add all survivors from right_stack (those who were never popped) with their updated health.
    for health, idx in right_stack:
        survivors.append((idx, health))
    
    # Prepare the final answer in the original input order.
    survivors.sort(key=lambda x: x[0])
    result = [health for _, health in survivors]
    return result

# Example test cases
print(robotCollisions([5,4,3,2,1], [2,17,9,15,10], "RRRRR"))  # Expected: [2,17,9,15,10]
print(robotCollisions([3,5,2,6], [10,10,15,12], "RLRL"))         # Expected: [14]
print(robotCollisions([1,2,5,6], [10,10,11,11], "RLRL"))         # Expected: []