Gas Station
Find the station to start a circular tour without running out of gas. If the running tank ever goes negative, no station up to and including the current one could have worked, so restart the candidate at the next station.
- Category
- Greedy
- Time complexity
- O(n)
- Space complexity
- O(1)
Pseudocode
tank ← 0, start ← 0 for each station: tank += gas[i] − cost[i] if tank < 0: start ← i+1, tank ← 0 feasible iff total gas ≥ total cost
Reference implementation
tank = total = start = 0
for i in range(n):
diff = gas[i] - cost[i]
tank += diff; total += diff
if tank < 0: start = i + 1; tank = 0
return start if total >= 0 else -1