gasStationII.py

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

# Note:
# The solution is guaranteed to be unique.

class Solution:
    # @param gas, a list of integers
    # @param cost, a list of integers
    # @return an integer
    def canCompleteCircuit(self, gas, cost):
        res = []
        tol, sumi, start = 0, 0, 0    
        for i in range(len(gas)): 
            res.append(gas[i]-cost[i])
            tol += res[i]
            if sumi < 0: 
               start = i
               sumi = res[i]
            else: sumi += res[i]
        return -1 if tol < 0 else start

if __name__ == '__main__':
   gas = [5, 2, 4]
   cost = [2, 3, 4]
   test = Solution()
   out = test.canCompleteCircuit(gas, cost)
   print out