Description
At each station on a circular route, collect gas[i] and spend cost[i] to reach the next station. With an empty initial tank, return a starting station that completes one circuit, or -1 if none exists. Assume a successful start is unique.
Solution
def can_complete_circuit(gas, cost):
start = tank = total = 0
for i, (fuel, expense) in enumerate(zip(gas, cost)):
difference = fuel - expense
total += difference
tank += difference
if tank < 0:
start = i + 1
tank = 0
return start if total >= 0 else -1Examples
Example 1
- Input
[[1,2,3,4,5],[3,4,5,1,2]]- Output
3
Starting at 3 accumulates enough gas for the full loop.
Example 2
- Input
[[2,3,4],[3,4,3]]- Output
-1
The total gas is insufficient.
Example 3
- Input
[[2],[1]]- Output
0
The single station covers its travel cost.
Approach
Accumulate total gas minus cost and a running tank from the current candidate. If that tank becomes negative, every start since the candidate fails at this point, so try the next station. A nonnegative total guarantees the final candidate succeeds.
Time & space
O(n) time and O(1) auxiliary space, where n is station count.