Robot Collisions

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, where 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 it survived, final health of robot 2 if it 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
Inputpositions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
Output[2,17,9,15,10]
No collision occurs because all robots are moving in the same direction, so the original healths are returned in input order.
Example 2
Inputpositions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"
Output[14]
Robot 1 and robot 2 remove each other, then robot 3 defeats robot 4 and its health decreases from 15 to 14, leaving only robot 3.

Constraints

  • 1 <= positions.length == healths.length == directions.length == n <= 10^5
  • 1 <= positions[i], healths[i] <= 10^9
  • directions[i] == 'L' or directions[i] == 'R'
  • All values in positions are distinct

Asked at 6 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate