134.Gas Station

There areNgas stations along a circular route, where the amount of gas at stationiisgas[i].

You have a car with an unlimited gas tank and it costscost[i]of gas to travel from stationito 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.
Method 1 Greedy, O(n) time, O(1) space

• First check if sum of gas is less than sum of cost if yes, there can be no answer.
• Loop through Gas and Cost, if an index does not provide enough gas, set the result to the next index and try that.

class Solution(object):
    def canCompleteCircuit(self, gas, cost):"""
        if sum(gas) < sum(cost):
            return -1
        res = 0
        cur = 0
        for i, amt in enumerate(gas):
            cur += amt
            cur -= cost[i]
            if cur < 0:
                res = i+1
                cur = 0

        return res