Gas Station

NeetCode: Gas Station · LeetCode: 134. Gas Station · Difficulty: Medium

There are n gas stations on a circle. Station i gives gas[i] fuel and driving from i to the next station costs cost[i]. The tank starts empty. Return the index of the station from which you can complete one full clockwise loop, or -1 if impossible. The answer is unique if it exists.

Example

Text

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

Brute force: simulate from every start

Try each station as the start and simulate the whole loop, giving up when the tank goes negative.

Java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean ok = true;
            for (int step = 0; step < n; step++) {
                int i = (start + step) % n;
                tank += gas[i] - cost[i];
                if (tank < 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return start;
            }
        }
        return -1;
    }
}

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

Output

3
-1
0

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

Java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int tank = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            tank += diff;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total < 0 ? -1 : start;
    }
}

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

Output

3
-1
0

The running sums are int values. They wrap silently on overflow, which the problem's input limits are small enough to avoid. Time: O(n). Space: O(1).