Full circle road trip
Find the station from which a car can drive once around a ring road, by restarting from the next station whenever the tank would go empty. About 20 minutes.
Total fuel decides if it is possible
A ring road has stations. At each station you take some litres from the pump, and driving on to the next station burns some litres. The tank starts empty and has no limit.
First check: if all the fuel you can collect is less than all the fuel the trip burns, no start can work. If the fuel is at least the cost, some start must work, because the trip is a circle.
Restart after a failure
Try station 0 as the start and drive on, tracking the tank. If the tank goes negative at station i, the trip from station 0 fails. Worse, any start between 0 and i also fails, since each of those arrives at i with even less fuel than a start at 0 would.
So jump to i + 1 as the next candidate and reset the tank. Scan once around, and the last candidate wins.
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0Start at 0: the tank is 2 after station 0, then 0 after station 1.
Total gas is 10 and total cost is 12. What is the answer?
- ANo start works: return −1
- BStart at station 0
- CStart at the last station
Show the answer
No start works: return −1. You can never collect enough fuel to pay for the whole circle.
Full circle trip
A ring road has n stations. At station i you collect gas[i] litres of fuel, and driving from station i to the next one costs cost[i] litres. Your tank has no limit and starts empty. Return the smallest index of a station from which you can drive once all the way around, or −1 if no start works.
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] → 3
1 ≤ n ≤ 100,000 · 0 ≤ gas[i], cost[i] ≤ 10,000