• n == gas.length == cost.length
• 1 ≤ n ≤ 10⁵
• 0 ≤ gas[i], cost[i] ≤ 10⁴
• The tank is unlimited in size and starts empty
• If an answer exists it is unique

Stations sit in a circle. At each one you gain gas[i] fuel and then spend cost[i] to reach the next. Starting empty at a station of your choosing, can you drive all the way around back to where you began without the tank ever going negative? If yes, from where?

The only thing that matters at each leg is the net change, gas[i] - cost[i]. A leg with more gas than cost fills you up; a leg with more cost than gas drains you. So really you are walking a circle of positive and negative numbers, and you need a starting point from which the running sum never dips below zero.

Try every station as a start and simulate the loop:

def can_complete(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        for k in range(n):
            i = (start + k) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                break
        else:
            return start          # completed a full loop
    return -1

With up to 100000 stations this is O(N²) — ten billion steps in the worst case, far too slow. The waste is that each restart throws away everything the previous simulation learned. We will now extract two facts that let a single pass replace all those restarts.

Observation 1 — feasibility is decided by the grand total. Add up every gas[i] - cost[i] around the whole circle. If that total is negative, you burn more than you carry no matter where you start, so the answer is -1. If it is zero or positive, a valid start is guaranteed to exist. This single number answers the yes/no question completely, independent of where you start.

Observation 2 — the pivot rule tells you where. Suppose you start at station A and, running the tank forward, you first go negative when arriving at station B. Then no station from A up to B can be a valid start. Here is why, and it is worth following. You started at A with an empty tank and stayed non-negative all the way until B broke it. Now pick any station C strictly between A and B as a fresh start. When you originally passed through C, your tank was some non-negative amount; starting at C instead means starting with zero there — less fuel, never more. So if the stretch from C to B drained the tank even with that extra cushion, it will certainly drain it starting from empty. Every station in A..B fails at B or sooner. So the only candidate worth trying next is B + 1.

Put the two together: sweep once. Keep a running tank for the current candidate start. Whenever tank goes negative at station i, you have just learned that the current candidate and everyone up to i are impossible, so jump the candidate start to i + 1 and reset tank to 0. Separately keep the grand total to decide feasibility at the end.

def can_complete(gas, cost):
    total = 0            # decides whether ANY start works
    tank = 0             # fuel for the current candidate start
    start = 0
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0:              # current start (and all since) is doomed
            start = i + 1         # pivot to the next station
            tank = 0              # fresh empty tank from there
    return start if total >= 0 else -1

O(N) time, O(1) space, one loop.

Loop ends. total = 0 ≥ 0, so answer is start = 3. Verify by hand starting at station 3: tank goes 3 → 6 → 4 → 2 → 0, never negative, full loop complete.

And the impossible case, gas = [2,3,4], cost = [3,4,3]: diffs -1,-1,+1, grand total = −1 < 0, so −1 — you simply do not carry enough fuel for the loop, wherever you begin.

This problem teaches a specific and reusable greedy move: when a failure at position B rules out an entire prefix of candidates, skip straight past it instead of retrying them one by one. The formal name for the reasoning is the same exchange-style argument from the other greedy pages — you prove that none of the skipped candidates could beat the one you jump to, so discarding them is safe.

The recognition signal: you are looking for a starting point on a sequence (often circular) from which a running accumulator stays within some bound. Whenever a run of the accumulator dies at a specific point, ask "does that failure also condemn everything I passed on the way?" If yes, you have a linear one-pass greedy instead of a quadratic search. The same shape appears in maximum-subarray (Kadane's algorithm resets its running sum on going negative for exactly this reason) and in several sliding-window problems.

The second habit: separate the global feasibility question from the local search. Here one number decided whether an answer exists and a separate scan decided where. Splitting "does it exist?" from "where is it?" often simplifies these problems dramatically.