Leetcode 134. Gas Station

https://leetcode.com/problems/gas-station/

The solution is first make sure the sum of gas is greater or equal than the cost; then try to start from every station and go around.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param gas, a list of integers
    # @param cost, a list of integers
    # @return an integer
    def canCompleteCircuit(self, gas, cost):
        if sum(gas) < sum(cost): return -1
        n, diff, stationIndex = len(gas), 0, 0
        for i in range(n):
            if gas[i]+diff < cost[i]: 
                stationIndex, diff = i+1, 0
            else: diff += gas[i]-cost[i]
        return stationIndex

Run Time: 48 ms