Medium Greedy Choice Greedy
In plain English: Find which gas station to start at so you can drive around a circular route without running out of fuel.
If total gas >= total cost, a solution exists. Track the running surplus — whenever it goes negative, the answer must be past that point.
Prompt
There are n gas stations in a circle. Given gas[i] and cost[i], find the starting station index for a complete circuit, or -1 if impossible.
Try to write it from scratch before scrolling down.
Solution
def can_complete_circuit(gas, cost):
total = 0
tank = 0
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1 # can't start at or before i
tank = 0
return start if total >= 0 else -1
# Test: can_complete_circuit([1,2,3,4,5],[3,4,5,1,2]) == 3
# Test: can_complete_circuit([2,3,4],[3,4,3]) == -1