Circular Fuel Route
Problem
Fuel stations sit on a circular road. Station i lets you take on fuel[i] units, and driving from station i to the next one burns cost[i] units. You start at one station with an empty tank and drive all the way round, never letting the tank drop below zero. Return the index of the first station from which the full loop succeeds, or -1 if none does.
Examples
Input: fuel = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Why: from station 3 the tank reads 3, 6, 4, 2, 0 after each legInput: fuel = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Why: 9 units of fuel cannot pay for 10 units of drivingInput: fuel = [5], cost = [4]
Output: 0
Why: edge case, a single station only has to pay for its own loopHints
0 / 3
Simulating the loop from every station works in quadratic time. Start by finding a quick test for whether any start can work at all.
If a trip that started at station s runs dry just after station i, then starting at any station between s and i is no better, because you would reach i with no more fuel than you had.
If total fuel is less than total cost, return -1. Otherwise sweep once with a running tank and a candidate start. Whenever the tank goes negative after station i, move the candidate to i + 1 and reset the tank to zero. The candidate left at the end is the answer.
Solution
If the fuel on the whole road is less than the driving it has to pay for, no start can work. Otherwise a single sweep suffices: a trip from s that fails right after station i arrived at every intermediate station with a non-negative tank, so starting at one of them only throws that surplus away and fails too. The candidate therefore jumps past the failure point, and every index it skips is provably bad, which also makes the survivor the lowest working index. The total-fuel check guarantees the survivor completes the loop. Time is O(n) and space is O(1).
def start_station(fuel, cost):
if sum(fuel) < sum(cost):
return -1 # not enough fuel on the whole road
start, tank = 0, 0
for i in range(len(fuel)):
tank += fuel[i] - cost[i]
if tank < 0: # every start from start..i fails here
start, tank = i + 1, 0
return start
print(start_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])) # -> 3
print(start_station([2, 3, 4], [3, 4, 3])) # -> -1
print(start_station([5], [4])) # -> 0Stuck on the idea rather than the code? Gas Station covers it.