Gas Station

One failed trip can rule out a whole block of starting stations, not just the one you tried.

Try every station

Start at each station and simulate up to n legs. Stop a simulation as soon as its tank goes negative; if one survives all n legs, return that start.

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    n = len(gas)
    for start in range(n):
        tank = 0
        for step in range(n):
            station = (start + step) % n
            tank += gas[station] - cost[station]
            if tank < 0:
                break
        else:
            return start
    return -1

Time O(n²) — up to n starts each drive n legs. Space O(1) — the simulation stores only its tank and indices.

Reset failed candidates

Scan the stations once as if the route were laid flat. tank holds the fuel balance since the current candidate start. If it becomes negative after station i, discard the whole stretch and try i + 1. A separate total balance decides whether any full circuit is possible at all.

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    total = 0
    tank = 0
    start = 0
 
    for i in range(len(gas)):
        balance = gas[i] - cost[i]
        total += balance
        tank += balance
        if tank < 0:
            start = i + 1
            tank = 0
 
    return start if total >= 0 else -1

The exchange argument is a proof that swapping rejected choices for the greedy choice can't remove a global optimum. Suppose start first fails at station i. Before every intermediate station k, the tank from start was non-negative. Removing that non-negative prefix makes the balance from k through i no larger, so k also fails by i. Exchange every candidate in that failed block for i + 1; none of the discarded starts could be the answer. Repeating this leaves the only globally viable candidate. If total < 0, the route consumes more fuel than all stations provide, so no start works; if total >= 0, the surviving candidate completes the loop and is globally optimal.

Time O(n) — each station is processed once. Space O(1) — the candidate and two balances carry the proof.