Leetcode[134] Gas Station

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

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        N = len(gas)
        diff = [gas[i] - cost[i] for i in range(N)]
        res = -1
        total = 0
        local = 0
        for i in range(N):
            local += diff[i]
            total += diff[i]
            if local < 0:
                local = 0
                res = i
        return res + 1 if total >= 0 else -1

###Java

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //edge casa
        if (gas == null || cost == null || gas.length != cost.length) {
        	return -1; 
        }

        int N = gas.length;
        int total = 0;
        int sum = 0;
        int diff = 0;
        int res = -1;
        for (int i = 0; i < N; i++) {
            diff = gas[i] - cost[i];
            sum += diff;
            total += diff;

            if (sum < 0) {
                sum = 0;
                res = i;
            }
        }

        return total < 0 ? -1 : res + 1;
    }
}

###Points

• O(n)
• Total determine if route exists; local determine start from where: once local less than 0, start from the next station.