Gas Station

Brute Force

Time O(n²)Space O(1)

Try every station as a starting point and simulate the full lap, bailing out as soon as the tank goes negative.

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        n = len(gas)
        for start in range(n):
            tank = 0
            steps = 0
            i = start
            while steps < n:
                tank += gas[i] - cost[i]
                if tank < 0:
                    break
                i = (i + 1) % n
                steps += 1
            if steps == n:
                return start
        return -1

Each of the n candidate starts can simulate up to n steps, so this is O(n²) time in the worst case.

Greedy: One Pass with Reset

OptimalTime O(n)Space O(1)

Two facts make a single pass enough. First, a valid start exists at all only if sum(gas) >= sum(cost) — total supply must cover total demand. Second, if starting at station s and driving forward causes the running tank total to first go negative at some station i, then no station between s and i (inclusive) can be a valid start either — each of them would arrive at that same failure point with an equal or smaller tank, since starting later only throws away gas s had already banked. So the moment the running total dips below zero, discard every station tried so far and restart the candidate at the very next station.

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        total = 0
        start = 0
        for i in range(len(gas)):
            total += gas[i] - cost[i]
            if total < 0:
                start = i + 1
                total = 0
        return start

Tracing gas = [1,2,3,4,5], cost = [3,4,5,1,2]:

Watch how the banked-fuel row is measured from the current candidate start: the first station where it dips below zero proves the whole run since that start cannot work, so the candidate jumps past all of it and the fuel counter resets.

total gas = 15total cost = 15supply covers demand

i=0-2·

i=1-2·

i=2-2·

i=3+3·

i=4+3·

top chip: net fuel (gas − cost) · bottom chip: fuel banked since the candidate start

running tank

candidate start

scan i

1 / 7

currentseenresultdiscarded

15 >= 15, so supply covers demand and a valid start must exist. Scan stations left to right while banking net fuel from the candidate start.

Why it’s correct: the check sum(gas) >= sum(cost) guarantees some start works; the reset rule guarantees the loop lands on it, because every station that fails is provably not the answer (proven above), so skipping past all of them loses no valid candidate. Complexity: one pass, two running variables → O(n) time, O(1) space.

Brute Force

Greedy: One Pass with Reset

More Greedy practice