0475HardArrayStackSortingSimulation

Freight Trolleys on One Rail

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n log n), dominated by ordering the trolleys along the railSpace O(n) for the ordering, the working charges and the stack

Order the trolleys along the rail, low end first, and walk them once. A trolley set towards the high end can only ever be met by something further along, so park it on a stack. A trolley set towards the low end settles with the stack from the top down: each comparison either ends that trolley, or clears the stack top and continues, or ends both. Charges are edited in a working copy indexed by the original position in the input, so the answer is read off in listing order at the end.

Pythonentry point: surviving_charges

def surviving_charges(spots, charge, headings):
    # Sweep the rail from one end; the trolleys still rolling right are exactly the
    # ones a newly met left-roller can hit, most recent first, so keep them on a stack.
    # time O(n log n) for the ordering, space O(n)
    order = sorted(range(len(spots)), key=lambda i: spots[i])
    left = list(charge)
    rolling_right = []
    for i in order:
        if headings[i] == "R":
            rolling_right.append(i)
            continue
        standing = True
        while standing and rolling_right:
            j = rolling_right[-1]
            if left[j] > left[i]:
                left[j] -= 1
                left[i] = 0
                standing = False
            elif left[j] < left[i]:
                left[i] -= 1
                left[j] = 0
                rolling_right.pop()
            else:
                left[i] = 0
                left[j] = 0
                rolling_right.pop()
                standing = False
    return [left[i] for i in range(len(spots)) if left[i] > 0]

The obvious version

Simulate meetings one at a time. Repeatedly rebuild the list of trolleys still on the rail in rail order, find the first neighbouring pair set towards each other, apply the meeting rule to it, and start over. Stop when no such neighbouring pair is left.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_surviving_charges(spots, charge, headings):
    order = sorted(range(len(spots)), key=lambda i: spots[i])
    hp = list(charge)
    while True:
        rolling = [i for i in order if hp[i] > 0]
        pair = -1
        for p in range(len(rolling) - 1):
            if headings[rolling[p]] == "R" and headings[rolling[p + 1]] == "L":
                pair = p
                break
        if pair < 0:
            break
        a = rolling[pair]
        b = rolling[pair + 1]
        if hp[a] > hp[b]:
            hp[a] -= 1
            hp[b] = 0
        elif hp[a] < hp[b]:
            hp[b] -= 1
            hp[a] = 0
        else:
            hp[a] = 0
            hp[b] = 0
    return [hp[i] for i in range(len(spots)) if hp[i] > 0]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in