There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
class Solution(object): def canCompleteCircuit(self, gas, cost): """ :type gas: List[int] :type cost: List[int] :rtype: int """ """ 1. Prove: If sum(gas) >= sum(cost) there must be a loop if we start from a and have to stop at b then sum(gas[a,b]) < sum(cost[a,b]) and now we have sum(gas[b,a]) > sum(cost[b,a]) and sum(gas[b,a]) - sum(cost[b,a]) > sum(cost[a,b]) - sum(gas[a,b]) so we start from b and must be able to finish the loop 2. description of algorithm assum we start somewhere and must pass by point C. then if we can finish the loop, we have: gas accumulated in [start,C] must bigger than gas consume in [C, end] 1. choose a point C, sum = C, i,j = C+1,C-1 while i != j: if sum > 0: # we are able to move, move forward sum += diff[i] i = (i+1)%n if sum <=0: # we need to accumulate more gas before sum += diff[j] j = (j+n-1)%n sum += diff[i] # i == j if sum > 0: return i # start from i, the gas we accumulate before C can support us to finish the circle else: return -1 # sum(gas) < sum(cost) with C = 0 (or say len(n)-1), so easy. """ i,j, sum = 0, len(gas)-1, 0 while i < j: if sum >0: sum += gas[i] - cost[i] i += 1 else: sum += gas[j] - cost[j] j -= 1 sum += gas[i] - cost[i] if sum < 0: return -1 elif gas[i] - cost[i] >= 0: # if we can accumulate gas, start here return i else: return i+1 # else we must be able to accumulate gas here