#2751

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Robot Collisions

Robot Collisions involves simulating robot movements and handling collisions with stack-based state management.

Problem Statement

You are given n robots, each with a position, health, and movement direction. Robots move simultaneously at the same speed in their given direction, and the directions are either 'L' (left) or 'R' (right). If two robots collide while moving to the same position, they engage in a fight where the one with less health is removed. If both have equal health, both are removed.

Your task is to simulate the robot movements and handle the collisions, returning the healths of the remaining robots after all collisions are resolved. Robots are processed in the order of their positions to ensure collisions are handled correctly. The problem demands a stack-based approach to efficiently manage robot states during the simulation.

Examples

Example 1

Input: positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"

Output: [2,17,9,15,10]

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]

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: []

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 <= 105
1 <= positions[i], healths[i] <= 109
directions[i] == 'L' or directions[i] == 'R'
All values in positions are distinct

Solution Approach

Sorting the Robots

Start by sorting the robots based on their positions to ensure collisions are processed in the correct order. Sorting helps maintain the natural flow of the simulation where robots from left to right are handled first.

Using a Stack for State Management

Use a stack to track robots that are still in play. As robots move, compare their states to handle collisions efficiently. When a robot moves to a position with another robot, resolve the collision based on health, updating the stack accordingly.

Final Health Calculation

After all robots have been processed, the stack will contain the remaining robots. The final health of each robot in the stack is returned as the solution.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log n)
Space	O(n)

The time complexity is O(n log n) due to the sorting step, and the space complexity is O(n) due to the stack usage for tracking robot states during the simulation.

What Interviewers Usually Probe

Candidate should demonstrate an understanding of stack-based state management.
Look for clarity in how the stack is used to handle the robots and their health adjustments.
Ensure the candidate emphasizes sorting the robots by position to process collisions correctly.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the robots correctly before processing collisions can lead to incorrect results.
Not properly handling edge cases where robots collide with equal health, resulting in both being removed.
Mismanaging the stack and leaving robots unprocessed or miscalculating their final health.

Follow-up variants

Change the robot movement speed or direction and observe how the solution adapts to different constraints.
Consider introducing more complex robot interaction rules, such as robots with special abilities or health modifiers.
Introduce obstacles in the robot path that block movement and modify how collisions are handled.

FAQ

What is the primary pattern for solving the Robot Collisions problem?

The primary pattern is stack-based state management, ensuring that robot positions and health are correctly tracked and updated during collisions.

How do I handle the sorting of robots?

Robots should be sorted by their positions before processing to ensure that collisions are handled from left to right as they move across the line.

Why is sorting necessary in Robot Collisions?

Sorting ensures robots are processed in the correct order, allowing for accurate collision resolution based on position and movement direction.

Can there be a situation where all robots are removed?

Yes, if robots collide and their healths are equal, both will be removed. If multiple such collisions occur, the result could be an empty array.

How does stack management improve efficiency in this problem?

Stack management allows for efficient tracking of robot states, ensuring that collisions are resolved and healths are updated without unnecessary recalculations.

terminal

Solution

Approach 1: Stack Simulation

We first sort the robots by position in ascending order, storing the sorted robot indices in an array $\textit{idx}$. We then use a stack to simulate the collision process:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def survivedRobotsHealths(self, positions, healths, directions):
        idx = sorted(range(len(positions)), key=lambda i: positions[i])
        stk = []

        for i in idx:
            if directions[i] == "R":
                stk.append(i)
                continue

            while stk and healths[i]:
                j = stk[-1]
                if healths[j] > healths[i]:
                    healths[j] -= 1
                    healths[i] = 0
                elif healths[j] < healths[i]:
                    healths[i] -= 1
                    healths[j] = 0
                    stk.pop()
                else:
                    healths[i] = healths[j] = 0
                    stk.pop()
                    break

        return [h for h in healths if h > 0]

Continue Practicing

#2736 maximum sum queries #2766 relocate marbles #2813 maximum elegance of a k length subsequence