0789EasyArrayStackQueueSimulation

Stranded at the Battery Swap

Tracked in this browser only

Trains the technique from

LeetCode 1700Number of Students Unable to Eat Lunch

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 scooter depot runs one battery swap station. Every scooter is fitted for exactly one of two pack formats, written as 0 or 1, and a scooter can only accept a charged pack of its own format.

The riders waiting to swap stand in a single line. riders[i] is the format the rider at position i needs, with riders[0] at the front of the line.

The charged packs sit in one vertical rack, and only the pack on top can be lifted off. rack lists the packs from the top downwards, so rack[0] is the pack currently on top and the last entry is the pack at the bottom. There are as many packs as riders.

The swap round runs like this, over and over:

The rider at the front of the line looks at the pack on top of the rack.
If that pack matches their format, they lift it off and leave the line. The next pack down becomes the top pack, and the next rider steps up to the front.
Otherwise they take nothing and walk to the back of the line, and the rider behind them steps up to the front.

The round finishes when the line is empty, or when the pack on top matches none of the formats needed by the riders still in the line. In that second case those riders keep circling for ever and none of them will be served.

Return how many riders are still in the line when the round finishes.

Examples

Example 1

Input: riders = [0, 1, 1, 0, 1], rack = [1, 1, 0, 0, 0]
Output: 1

The rider at the front needs format 0 and the top pack is a 1, so that rider goes to the back and the next one takes the top pack. The following pack, another 1, goes to the rider who is then at the front. Two 0 packs are next and the two riders needing format 0 take them, leaving one rider needing format 1 in front of a 0 pack, which that rider cannot use.

Example 2

Input: riders = [1, 1, 1], rack = [0, 1, 1]
Output: 3

Every rider in the line needs format 1 and the pack on top is a 0, so each rider in turn declines it and walks to the back. Nothing is ever lifted off the rack and all three riders are still in the line.

Example 3

Input: riders = [1, 0], rack = [0, 1]
Output: 0

The first rider needs format 1 and declines the 0 on top, so the second rider steps up and takes it. The 1 underneath then goes to the rider who moved to the back, and the line empties.

Constraints

1 <= riders.length <= 100
1 <= rack.length <= 100
riders.length == rack.length
0 <= riders[i] <= 1
0 <= rack[i] <= 1

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 count_stranded_riders(riders: list[int], rack: list[int]) -> int:

Java

public int countStrandedRiders(int[] riders, int[] rack)

The intended approach

Time O(n) for n riders: one pass over the line to tally and at most one pass down the rack.Space O(1), just the two format tallies.

Tally how many riders in the line need format `0` and how many need format `1`. The pack on top can be lifted off precisely when the tally for its format is still above zero, and whichever rider ends up taking it, the line is left with one fewer rider of that format. So walk the rack from the top down, spending one from the matching tally each time, and stop at the first pack whose tally has already run out. The two tallies then add up to the riders left circling.

Pythonentry point: count_stranded_riders

def count_stranded_riders(riders, rack):
    # A pack can leave the top of the rack exactly when at least one rider still in
    # the line is fitted for that format, so only the tally of the two formats still
    # wanted matters. Walk the rack from the top, spending a tally each time, and
    # stop at the first pack whose tally has run out.
    # Time O(n), space O(1) beyond the two tallies.
    waiting = [0, 0]
    for fmt in riders:
        waiting[fmt] += 1
    for fmt in rack:
        if waiting[fmt] == 0:
            break
        waiting[fmt] -= 1
    return waiting[0] + waiting[1]

The obvious version

Act the round out literally with two deques, one for the line and one for the rack, moving a declining rider to the back and counting consecutive declines. Once the number of consecutive declines reaches the length of the line, everyone still there has looked at the top pack and refused it, so the round is over and the line length is the answer.

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

from collections import deque


def bf_count_stranded_riders(riders, rack):
    line = deque(riders)
    packs = deque(rack)
    declined = 0
    while line and declined < len(line):
        if line[0] == packs[0]:
            line.popleft()
            packs.popleft()
            declined = 0
        else:
            line.append(line.popleft())
            declined += 1
    return len(line)

How this problem was checked

Reference solution executed against 18 test cases — 18 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