Show problems as
Classic problem #2751HardArrayStackSortingSimulation

Robot Collisions

Real-world version: Freight Trolleys on One Rail
Tracked in this browser only
Read Robot Collisions on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A warehouse runs n freight trolleys on one long straight rail. Trolley i is parked at spots[i], carries charge[i] units of battery, and is set to roll towards the low end of the rail when headings[i] is "L" or towards the high end when it is "R". No two trolleys are parked at the same place.

Every trolley is released at the same instant and they all roll at the same speed, so two trolleys meet only when they are set towards each other. Two trolleys rolling the same way never close on one another.

When two trolleys meet, the one carrying less battery is pulled off the rail and the other loses one unit of battery and carries on in the direction it was already going. If the two carry the same battery, both are pulled off. A trolley pulled off the rail plays no further part.

Return the remaining battery of the trolleys still on the rail once no further meetings are possible, listed in the order the trolleys appear in the input. Return an empty list when nothing survives.

Examples

Example 1

Input
spots = [3, 10, 20], charge = [4, 7, 2], headings = "RLR"
Output
[6, 2]

The trolley from index 0 and the one from index 1 close on each other; the weaker one leaves the rail and the other comes away with 6 units. Index 2 is set away from both and is never touched.

Example 2

Input
spots = [1, 4, 7, 10], charge = [10, 2, 3, 1], headings = "RLLL"
Output
[7]

Index 0 has far more battery than the three trolleys coming the other way and clears all three, ending on 7 units.

Example 3

Input
spots = [10, 1, 5], charge = [5, 9, 2], headings = "LRR"
Output
[8]

Index 0 is the only trolley set towards the low end. It clears index 2 and then loses to index 1, which finishes on 8 units.

Constraints

  • 1 <= spots.length == charge.length == len(headings) == n <= 10^5
  • 1 <= spots[i], charge[i] <= 10^9
  • headings[i] == 'L' or headings[i] == 'R'
  • All values in spots are distinct.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def surviving_charges(spots: list[int], charge: list[int], headings: str) -> list[int]:
Java
public List<Integer> survivingCharges(int[] spots, int[] charge, String headings)

More on the same topics