Gas Station: the idea to remember.

The core insight

Track total balance and a running tank; reset the start just after any point where the tank becomes negative.

Why it works

If the current candidate fails at an index, every later candidate before that index also lacks enough gas to pass it.

The mistake to avoid

The total gas balance must be nonnegative; a locally promising station alone is not sufficient.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Track total balance and a running tank; reset the start just after any point where the tank becomes negative.
public int canCompleteCircuit(int[] gas, int[] cost) {
    int sGas = 0, sCost = 0, res = 0, total = 0;
    for (int i = 0; i < gas.length; i++) {
        sGas += gas[i];
        sCost += cost[i];
    }
    if (sGas < sCost) return -1;
    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
        if (total < 0) {
            total = 0;
            res = i + 1;
        }
    }
    return res;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection