Gas Station: Greedy Circuit Traversal

Given n gas stations along a circular route with gas[i] fuel available and cost[i] fuel needed to reach the next station, find the starting station index that lets you complete the full circuit. If no such start exists, return -1.

This is LeetCode 134: Gas Station, a medium problem that looks like it needs simulation or brute force but actually yields to a clean greedy algorithm. The key insight is that you never need to backtrack. One pass through the array is enough.

Why this problem matters

Gas station LeetCode 134 is one of the best examples of the greedy-reset pattern. You try a candidate starting point, track a running total, and the moment the total goes negative, you reset your candidate to the next station. This same pattern appears in problems involving circular arrays, resource allocation, and scheduling.

The problem also tests two ideas at once: can you find the right start, and can you prove that a valid start even exists? The greedy approach handles both in a single scan.

The brute force approach

The most obvious solution is to try every station as a starting point. For each candidate start, simulate the full circuit and check if the tank ever goes negative.

def can_complete_circuit_brute(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        complete = True
        for j in range(n):
            station = (start + j) % n
            tank += gas[station] - cost[station]
            if tank < 0:
                complete = False
                break
        if complete:
            return start
    return -1

This works, but it runs in O(n^2) time. For each of the n possible starts, you simulate up to n steps. On large inputs (up to 10^5 stations), this is too slow. The problem is that when a simulation fails at some station, you throw away everything you learned and start from scratch at the next candidate.

The key insight: greedy reset

Here is what makes the greedy algorithm work. Suppose you start at station s and your tank goes negative when you arrive at station k. That means the segment from s to k has a net fuel deficit. Every station between s and k would also fail as a starting point, because starting at any of them would mean you have even less fuel accumulated when you reach k.

So you can skip all of them and jump your candidate start directly to k + 1.

The second insight is the existence check. If the total gas across all stations is at least the total cost, then a valid starting point must exist. The problem guarantees the solution is unique when it exists, so you only need to find one candidate that survives the full scan.

Combining these two ideas gives a one-pass O(n) algorithm:

1. Walk through every station once.
2. Track a running tank (fuel surplus since the current candidate start).
3. If tank goes negative, reset the candidate start to the next station and reset tank to 0.
4. Separately track the total surplus across all stations. If total is negative at the end, return -1. Otherwise, return the candidate start.

Walking through it step by step

Let's trace through the example gas = [1,2,3,4,5], cost = [3,4,5,1,2]. The net gain at each station is [-2, -2, -2, +3, +3].

The algorithm tries station 0, fails immediately (tank goes to -2), resets to station 1, fails again, resets to 2, fails again, then resets to station 3. From station 3, the tank stays non-negative through the rest of the scan. The total gas (15) equals the total cost (15), so a solution exists. The answer is station 3.

The greedy solution

Here is the complete solution in Python:

def can_complete_circuit(gas, cost):
    total = 0
    tank = 0
    start = 0

    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0:
            start = i + 1
            tank = 0

    return start if total >= 0 else -1

Four variables, one loop. Here is what each piece does:

1. total accumulates the global surplus. At the end, if total is negative, there is simply not enough gas to complete any circuit. Return -1.
2. tank tracks the fuel surplus since the current candidate start. It resets to 0 every time a new candidate is chosen.
3. start is the current candidate starting station. It advances past every station that causes a deficit.
4. The loop processes each station exactly once. When tank drops below 0, we know stations start through i cannot be the answer, so we move start to i + 1.

Why the greedy approach is correct

The correctness rests on two claims.

Claim 1: If starting at station s causes the tank to go negative at station k, then no station between s and k (inclusive) can be a valid start.

Proof sketch: at station s, the tank is 0. By the time you reach any station m between s and k, you have accumulated some non-negative surplus (otherwise you would have failed earlier). Starting at m means you begin with 0 instead of that surplus, so you would run out of fuel even sooner.

Claim 2: If total gas is at least total cost, a valid start exists.

Proof sketch: the total surplus across all stations is non-negative. The running surplus must dip below zero somewhere (otherwise station 0 works). The station right after the deepest valley in the running surplus is the optimal start, because it avoids the worst deficit segment.

Together, these two claims guarantee that the greedy candidate found by the algorithm is correct whenever a solution exists.

Complexity analysis

This is optimal. You need to inspect every station at least once, so O(n) is the lower bound. And O(1) space means no extra data structures.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy-reset pattern

The pattern of maintaining a running accumulator and resetting it when it violates a constraint:

candidate = 0
accumulator = 0
for i in range(n):
    accumulator += value(i)
    if accumulator < 0:
        candidate = i + 1
        accumulator = 0

In Gas Station, the accumulator is the fuel tank and the candidate is the starting station. In Maximum Subarray (Kadane's algorithm), the accumulator is the running subarray sum and you restart when it drops below the current element. The skeleton is the same. Only the accumulation logic and reset condition change.

2. Circular-array traversal

The pattern of treating a linear array as a circular route using modular arithmetic. In this problem, the circuit wraps from station n-1 back to station 0. The greedy solution avoids explicit modular indexing by making a clever observation: a single forward pass is enough because the total surplus check handles the wraparound implicitly. But in simulation-based approaches, you would use (start + j) % n to index into the circular route.

This pattern shows up in problems like Rotate Array, Circular Queue, and any problem where the end of the array connects back to the beginning.

Edge cases

Before submitting, make sure your solution handles these:

• Single station gas = [5], cost = [4]: net is positive, return 0. If gas = [3], cost = [5], total is negative, return -1.
• All stations have equal gas and cost gas = [3,3,3], cost = [3,3,3]: every station has net 0, tank never goes negative. Any start works, and the algorithm returns 0.
• Solution is the last station: the algorithm correctly sets start to n-1 if all earlier candidates fail. The total check confirms validity.
• Total gas equals total cost exactly: a solution still exists. The total >= 0 check uses greater-than-or-equal, not strictly greater.

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Forgetting the total check. If you only track the local tank and return start without verifying total >= 0, you will return a wrong answer when no valid start exists at all.

2. Off-by-one on the reset. When tank goes negative at index i, the new candidate start should be i + 1, not i. Station i itself is part of the failing segment.

3. Using modular simulation. Some people try to simulate the full circuit from the candidate start using modular indexing. This works but adds complexity and can degrade to O(n^2) if you are not careful about when to stop. The single-pass greedy approach avoids this entirely.

4. Confusing net gain with absolute values. The algorithm operates on gas[i] - cost[i], not on gas[i] or cost[i] individually. Make sure you compute the difference.

From understanding to recall

You have read the greedy solution and it makes sense. One pass, one reset rule, one total check. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: initializing tank and total to 0, resetting tank to 0 (not to diff), setting start = i + 1 (not i). These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy-reset loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "circular route, find valid start" and the code flows out without hesitation.

The greedy-reset pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Jump Game - Another greedy problem where tracking a running value replaces brute-force simulation
• Maximum Subarray - Kadane's algorithm uses the same "extend or restart" greedy-reset logic

CodeBricks breaks the gas station LeetCode problem into its greedy-reset and circular-array building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy algorithm question shows up in your interview, you do not think about it. You just write it.