Medium Circular Scan Greedy
In plain English: Find the 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 running tank — if it goes negative, the start must be past this point (reset). The greedy insight: the station after the worst deficit is the answer.
Prompt
There are n gas stations in a circle. gas[i] is the fuel at station i, cost[i] is fuel to travel to station i+1. Return the starting station index to complete the circuit, or -1 if impossible.
Try to write it from scratch before scrolling down.
Solution
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
tank = 0
start = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1 # can't start at or before i
tank = 0
return start
# 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