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.

Solution.

We set diff[i] = gas[i] – cost[i]. First of all, there is always a result if total sum of diff is greater than 0, or there won’t be a result.

Consider below cases:

gas[]  = [3,  2,  0, 0,   1,  2,  2]
cost[] = [2,  1,  1,  1,   2,  3,  0]
diff[] =  [1,  1, -1, -1, -1, -1,  2]

Let’s consider about diff[]. Basically, we need to find a point i in diff. And starting from this point i, move after it and count sum[diff[i], … ]. In this process, any j which is “behind” i should have sum[diff[i], …, diff[j]] >= 0. 

We have this assumption for point i: if j is the first element “behind” i which makes sum[diff[i], …, diff[j]] < 0, then any element between (i, j) has sum[diff[i], …, diff[k]] < 0.

Let’s do a rough assumption by using a line. j is the first element after i, which makes sum[i….j] < 0. So we have sum[i…j] < 0, sum[i…k] >= 0

Besides we know sum[i…j] = sum[i…k] + sum[k…j]. So we can conclude that sum[k…j] < 0.

Once we know this, we just do the sum of diff. Whenever the sum is less than zero, we set target to next element. Until we find an element which makes the sum is greater than 0 toward the end.

public int canCompleteCircuit(int[] gas, int[] cost) {
    // test see if there is a result.
    int total = 0;
    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
    }
    if (total < 0) {
        return -1;
    }
    // calculate the aggregation until we find a position which the aggregation from it to the end is greater than or equal to 0
    int aggr = 0, ans = 0;
    for (int i = 0; i < gas.length; i++) {
        aggr += gas[i] - cost[i];
        if (aggr < 0) {
            ans = i + 1;
            aggr = 0;
        }
    }
    return ans;
}

Check my code on github.