217. Gas Station Circuit

Why this mechanism works

Track global surplus separately from the current candidate's tank. If the candidate fails at i, every station between that candidate and i also fails: their skipped prefix had nonnegative surplus, so starting later cannot repair the negative remainder to i. Discard that entire block and try i+1.

State and boundaries

total is the whole processed surplus. tank is the surplus from candidate through the current station; every earlier candidate in discarded blocks has been disproved.

Protocol

1. Reject empty input.
2. Add gas[i]-cost[i] to total and tank.
3. When tank<0 move candidate to i+1 and reset tank.
4. Return candidate if total>=0, otherwise -1.

Visualization

net [-2,-2,-2,3,3]
failed blocks move candidate to 1,2,3
total=0; start 3 survives the suffix and wraparound

Python implementation

def gas_station(gas, cost):
    if not gas:
        return -1
    total = tank = candidate = 0
    for i in range(len(gas)):
        surplus = gas[i] - cost[i]
        total += surplus
        tank += surplus
        if tank < 0:
            candidate = i + 1
            tank = 0
    return candidate if total >= 0 else -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 gas_station: if not gas:
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]

L4 gas_station: total = tank = candidate = 0
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=0; tank=0; candidate=0

L5 gas_station: for i in range(len(gas)):
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=0; tank=0; candidate=0; i=0

L6 gas_station: surplus = gas[i] - cost[i]
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=0; tank=0; candidate=0; i=0; surplus=-2

L7 gas_station: total += surplus
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=-2; tank=0; candidate=0; i=0; surplus=-2

L8 gas_station: tank += surplus
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=-2; tank=-2; candidate=0; i=0; surplus=-2

L10 gas_station: candidate = i + 1
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=-2; tank=-2; candidate=1; i=0; surplus=-2

L11 gas_station: tank = 0
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=-2; tank=0; candidate=1; i=0; surplus=-2

... 13 intermediate state changes omitted ...

L8 gas_station: tank += surplus
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=-3; tank=3; candidate=3; i=3; surplus=3

L5 gas_station: for i in range(len(gas)):
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=-3; tank=3; candidate=3; i=4; surplus=3

L7 gas_station: total += surplus
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=0; tank=3; candidate=3; i=4; surplus=3

L8 gas_station: tank += surplus
gas=[1, 2, 3, 4, 5]; cost=[3, 4, 5, 1, 2]; total=0; tank=6; candidate=3; i=4; surplus=3

L2 gas_station: if not gas:
gas=[2, 3, 4]; cost=[3, 4, 3]

L4 gas_station: total = tank = candidate = 0
gas=[2, 3, 4]; cost=[3, 4, 3]; total=0; tank=0; candidate=0

L5 gas_station: for i in range(len(gas)):
gas=[2, 3, 4]; cost=[3, 4, 3]; total=0; tank=0; candidate=0; i=0

L6 gas_station: surplus = gas[i] - cost[i]
gas=[2, 3, 4]; cost=[3, 4, 3]; total=0; tank=0; candidate=0; i=0; surplus=-1

L7 gas_station: total += surplus
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-1; tank=0; candidate=0; i=0; surplus=-1

L8 gas_station: tank += surplus
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-1; tank=-1; candidate=0; i=0; surplus=-1

L10 gas_station: candidate = i + 1
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-1; tank=-1; candidate=1; i=0; surplus=-1

L11 gas_station: tank = 0
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-1; tank=0; candidate=1; i=0; surplus=-1

... 5 intermediate state changes omitted ...

L5 gas_station: for i in range(len(gas)):
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-2; tank=0; candidate=2; i=2; surplus=-1

L6 gas_station: surplus = gas[i] - cost[i]
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-2; tank=0; candidate=2; i=2; surplus=1

L7 gas_station: total += surplus
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-1; tank=0; candidate=2; i=2; surplus=1

L8 gas_station: tank += surplus
gas=[2, 3, 4]; cost=[3, 4, 3]; total=-1; tank=1; candidate=2; i=2; surplus=1

Why the solution is correct

A negative total makes any full circuit impossible. Each failed block eliminates all its possible starts by the prefix-surplus argument. The final candidate lies after a minimum cumulative-prefix boundary, so all subsequent cyclic partial sums are nonnegative when total is nonnegative. It therefore completes the circuit.

Time and space

O(n) time and O(1) auxiliary state.

Common mistakes

Resetting total with tank discards the global feasibility condition. A finite tank capacity changes the surplus argument.

Reasoning card

Transfer exercise

Return every feasible start using prefix sums and a sliding minimum over a doubled surplus array.