Ring Line Tram Battery
A city is testing a battery tram on its ring line. The stops are numbered 0 to n - 1 around the loop, and after the last stop the tram comes back to stop 0. Each stop has a charging pad that adds charge[i] units to the battery while the tram waits there. Driving from stop i to the next stop uses cost[i] units.
For the test run, the tram is placed at one stop with a flat battery. It charges there, drives on, charges at the next stop, and so on. The battery must never run out between stops. The engineers want to know where to place the tram so it can drive one full loop.
Your task
Write startingStop(charge, cost). The tram starts at stop s with 0 units, adds charge[s], spends cost[s] to reach the next stop, adds that stop's charge, and so on, until it is back at s. The battery level must never drop below 0 on arrival at a stop. Return the smallest stop index from which the full loop works, or -1 if none does.
The battery has no upper limit. Arriving with exactly 0 units is fine.
startingStop(charge: int[], cost: int[]) → int
Examples
charge = [3, 1, 2, 4] cost = [2, 3, 3, 1]
3
Start at stop 3: charge 4, drive costs 1, arrive at stop 0 with 3. Charge 3 (6), drive 2, arrive at stop 1 with 4. Charge 1 (5), drive 3, arrive at stop 2 with 2. Charge 2 (4), drive 3, arrive back at stop 3 with 1. Starting at stop 0 fails: 3 - 2 = 1, then 1 + 1 - 3 = -1 before stop 2. Stops 1 and 2 fail on their first drive.
charge = [2, 2, 2] cost = [3, 2, 2]
-1
All the pads together give 6 units, but the whole loop costs 7. No starting stop can make up for a loop that uses more than it gives.
Constraints
- 1 ≤ charge.length = cost.length ≤ 100,000
- 0 ≤ charge[i], cost[i] ≤ 10,000
Start with brute force
Try every stop as the start and simulate a full loop, stopping early if the battery goes negative. The first stop that completes the loop is the answer.
Each simulation can take up to n steps, so this is O(n²): with 100,000 stops that is up to 10 billion steps. The waste: when a run from stop 2 dies at stop 7, the brute force then tries stops 3, 4, 5 and 6, which are doomed for the same reason.
Hints
0 of 4 shown- Hint 1
Replace each stop by one number:
charge[i] - cost[i], the net gain of stopping there and driving on. In the first example that is[1, -2, -1, 3]. When is the loop impossible from every start? - Hint 2
If the net gains add up to less than 0, the answer is -1. It turns out that if they add up to 0 or more, some start always works. So the real question is which one.
- Hint 3
Start at stop 0 and drive, adding net gains. Suppose the battery first goes negative on the drive out of stop
i. Could any stop between your start andihave worked as a start instead? Each of them would reachiwith no more charge than you had. - Hint 4
Sweep once with a running
tankand a candidatestart = 0. Addcharge[i] - cost[i]; if the tank drops below 0, none of the stops fromstarttoican work, so setstart = i + 1andtank = 0. Separately add up the total net gain. Returnstartif the total is at least 0, otherwise -1.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Two facts make one pass enough.
- A failed run rules out its whole stretch. Say a run from
startdies leaving stopi. Any stopkin between was reached with a battery of 0 or more, so starting fresh atk(with 0) gives no more charge ati. It dies too. Skip straight toi + 1. - If the total net gain is at least 0, the last candidate works. The stretches you skipped all had negative sums, so the stretch from the final candidate to the end carries a surplus big enough to cover them on the way around.
Trace the first example. Net gains: [1, -2, -1, 3].
- i = 0: tank 1. Fine.
- i = 1: tank 1 - 2 = -1. Dead. Stops 0 and 1 are ruled out. start = 2, tank = 0.
- i = 2: tank -1. Dead. start = 3, tank = 0.
- i = 3: tank 3. Fine.
Total = 1 - 2 - 1 + 3 = 1 ≥ 0, so the answer is 3. Because every stop before the final candidate was ruled out, it is also the smallest stop that works.
function startingStop(charge, cost) {
let total = 0; // net gain of the whole loop
let tank = 0; // battery since the current candidate start
let start = 0;
for (let i = 0; i < charge.length; i++) {
const gain = charge[i] - cost[i];
total += gain;
tank += gain;
if (tank < 0) {
// No stop from start to i can work. Try the next one.
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}def starting_stop(charge, cost):
total = 0 # net gain of the whole loop
tank = 0 # battery since the current candidate start
start = 0
for i in range(len(charge)):
gain = charge[i] - cost[i]
total += gain
tank += gain
if tank < 0:
# No stop from start to i can work. Try the next one.
start = i + 1
tank = 0
return start if total >= 0 else -1Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.