Gas Station · DSA Prep

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] (net gas[i] - cost[i] shown in the array):

-2

total = -2start = 0

1 / 5

resultcurrentdiscarded

net[0] = 1-3 = -2. Running total goes negative — station 0 cannot be a valid start. Reset: start = 1.

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.