Python O(n) one pass with prove and explaination

• GasStation

###Q

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.
###A:

``````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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.