Gas Station

There are n gas stations on a circular route. Station i has gas[i] units of gas, and driving from station i to station i + 1 (wrapping from the last to the first) costs cost[i] units. The car has an unlimited tank and starts empty. Return the smallest index of a station from which the car can drive around the whole circuit once, or OptionalInt.empty() if there isn't one. OptionalInt is a container that holds either one int or nothing.

LeetCode: 134. Gas Station

Example

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
Output: 3

Start at 3: tank 4 - 1 = 3, at 4: 3 + 5 - 2 = 6, at 0: 6 + 1 - 3 = 4,
at 1: 4 + 2 - 4 = 2, at 2: 2 + 3 - 5 = 0, back at 3.

Brute force: simulate every start

import java.util.OptionalInt;

public class Main {
    static OptionalInt canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean ok = true;
            for (int k = 0; k < n; k++) {
                int i = (start + k) % n;
                tank += gas[i] - cost[i];
                if (tank < 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) return OptionalInt.of(start);
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
        System.out.println(canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
    }
}

OptionalInt[3]
OptionalInt.empty

Time: O(n²). Space: O(1).

Optimal: one greedy pass

Two facts make one pass enough:

1. If the total gas is at least the total cost, some start works. If it's less, none can.
2. If the tank goes negative when driving from start to station j, no station between start and j can be the start either. Each of those stations was reached with a tank of at least 0, so starting there with an empty tank would only have less gas at j. The next candidate is j + 1.

So drive once around the array. Whenever the tank goes negative, restart from the next station with an empty tank. If the overall total is non-negative, the last restart point is the answer.

import java.util.OptionalInt;

public class Main {
    static OptionalInt canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int gain = gas[i] - cost[i];
            total += gain;
            tank += gain;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? OptionalInt.of(start) : OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
        System.out.println(canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
        System.out.println(canCompleteCircuit(new int[]{5, 1, 2, 3, 4}, new int[]{4, 4, 1, 5, 1}));
        System.out.println(canCompleteCircuit(new int[]{3}, new int[]{3}));
    }
}

OptionalInt[3]
OptionalInt.empty
OptionalInt[4]
OptionalInt[0]

Time: O(n). Space: O(1).

The start found is also the smallest valid one. Suppose a valid start v existed before the returned one. The scan would have had to restart at some j >= v while driving from a start s <= v. But the stretch from s to v didn't go negative, and a valid v doesn't go negative on the stretch from v to j, so the tank at j couldn't have been negative.

Edge cases

• Total gas less than total cost: OptionalInt.empty(), no matter what the scan found.
• Single station: valid when gas[0] >= cost[0]. The last example in the code uses gas = [3] and cost = [3].
• Overflow: int sums wrap silently. For very large values, total and tank should be long.
• Restart past the last station (start == n): only happens when the total is negative, so it's never returned.