Gas Station

Find the station to start from to drive the whole circuit in one pass: restart just after any station where the tank runs dry.

The idea

Two facts make one pass enough. First, if the total gas is at least the total cost, some start works; if not, none does. Second, if you start at s and run dry right after station i, then no station between s and i can work either: you reached each of them with a tank of zero or more, so starting there fresh is never better. So whenever the tank goes negative, jump the candidate start to i + 1 and reset the tank.

Code

public static int CanCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.Length; i++) {
        total += gas[i] - cost[i];
        tank += gas[i] - cost[i];
        if (tank < 0) { start = i + 1; tank = 0; } // nobody from start..i gets past i
    }
    return total >= 0 ? start : -1;
}

Tips

• total decides IF there is an answer; the tank and its resets decide WHICH station it is.
• Each station is visited once, so the skipped stations are never retried - that is what makes it O(n) instead of O(n²).
• The problem promises the answer is unique when it exists, so the last start standing is the only candidate.

In the .NET library

Plain int is fine: at most 10⁵ stations with values up to 10⁴ keep the sums far from int.MaxValue.