[Leetcode] Gas Station

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.

The most naive method is to enumerate each position and loop the entire array to see if this position is valid or not. The time complexity is O(n^2). Actually we could use linear method to solve this problem since there exist many "waste check".

Image we start from some point say i, and we count the gas - cost from this point to j and find that we get a residual with negative, this means that we could not start from position and get j. In the naive method, we would move to i+1 and try again. However, we could skip to j+1 since i+1 would still give a negative residual. We would utilize this to speed up the algorithm.

1. First check if the total gas is larger than total cost, if not, we return -1.
2. If we start from some point i and reach to the end of the array with residual, this means this is the solution, since the solution is guaranteed to be unique.
3. If at some point j, we get negative residual, we skip i...j, start from j+1.

Why could we say that from point i, if we could reach to the end of the array, then this is the solution. Since if there is another point i' behind i (there is no solution in front of i) could reach to the end, but the solution is guarantee to be unique, then i and i' must be the same. And we have check that there could exist an solution.

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int[] dif = new int[n]; // store the difference of gas and cost
        int res = 0;
        for(int i = 0; i < n; i++) {
            dif[i] = gas[i] - cost[i];
            res += dif[i];
        }
        if(res < 0)
            return -1; // could not run the whole circle
        int ind1 = 0, ind2 = 0;
        while(ind1 < n) {
            int temp = 0;
            while(ind2 < n && temp >= 0) {
                temp += dif[ind2];
                ind2++;
            }
            if(temp < 0)
                ind1 = ind2; // have not finish the circle, could not reach the end
            else
                return ind1; // from here we could reach the end and since the solution is unique, this would be the solution
        }
        return -1;
    }