Lab 04 — Gas Station

Goal

Master the single-pass invariant greedy: O(n) time, O(1) space, with a non-trivial correctness invariant proving why we can skip ahead instead of retrying every starting station.

LC 134 is the canonical “one-pass with reset” greedy. The naive approach is O(n²): for each candidate starting station, simulate the trip. The greedy collapses this to O(n) via the invariant: if the running tank goes negative at station k starting from station s, then no station in [s, k] can be a valid starting point. Once you see this, the algorithm shrinks to a few lines and the proof is the entire test of skill.

Interview Context

Asked at Google, Bloomberg, Amazon. The candidate who codes O(n²) first then asks “can we do better?” is fine. The candidate who jumps to O(n) without the invariant proof is in danger — interviewers test by asking “why is start = k + 1 correct?” and a candidate without the invariant answers “uh, intuition.” That answer fails staff-level interviews.

Problem Statement

There are n gas stations on a circular route. Station i has gas[i] units of gas; traveling from station i to station i + 1 costs cost[i] units. Starting with an empty tank at some station, find the unique starting station that allows you to complete the full circle, or return -1 if impossible.

LeetCode reference: LC 134 — Gas Station.

Constraints

1 ≤ n ≤ 10^5
0 ≤ gas[i], cost[i] ≤ 10^4
The solution is unique if it exists.
Time O(n), space O(1).

Clarifying Questions

“Is the route guaranteed circular?” — yes; from station n - 1 you go to 0.
“Can the answer be ambiguous (multiple valid starts)?” — no, the problem guarantees uniqueness when a solution exists.
“Can gas[i] or cost[i] be negative?” — no, both non-negative.
“Should I return the index or the boolean feasibility?” — index, or -1.

Examples

gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3 (start at index 3: tank 0 + 4 - 1 = 3, 3 + 5 - 2 = 6, 6 + 1 - 3 = 4, 4 + 2 - 4 = 2, 2 + 3 - 5 = 0).
gas = [2,3,4], cost = [3,4,3] → -1 (total gas = 9, total cost = 10, infeasible).
gas = [5], cost = [4] → 0.
gas = [3,1,1], cost = [1,2,2] → 0.

Initial Brute Force

For each candidate start s, simulate the full trip; return the first s that succeeds.

def can_complete_brute(gas, cost):
    n = len(gas)
    for s in range(n):
        tank = 0
        for k in range(n):
            i = (s + k) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                break
        else:
            return s
    return -1

Brute Force Complexity

Time O(n²), space O(1). At n = 10^5, n² is 10^{10} — too slow.

Optimization Path

Brute — O(n²).
Total-feasibility check — if sum(gas) < sum(cost), no solution exists; return -1 immediately. Reduces wasted work but still O(n²) worst case.
One-pass with reset — O(n). The invariant below is the key.

Final Expected Approach

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

Data Structures Used

Two integers: start, tank. Plus the inputs.

Correctness Argument

We prove two things: (1) if sum(gas) ≥ sum(cost), the algorithm returns a valid starting index; (2) if sum(gas) < sum(cost), no solution exists.

Part 2 is trivial. Across one full lap, the tank changes by exactly sum(gas) - sum(cost). If this is negative, the tank cannot remain non-negative throughout any lap from any start — so no solution.

Part 1 — the key invariant.

Invariant (key claim): suppose we run the algorithm starting from index start = s and the running tank first goes negative at index k (so the partial sum tank after processing index k is < 0, but it was ≥ 0 after processing every index in [s, k - 1]). Then no index in [s, k] can be a valid starting point.

Proof of the key claim. Let T(a, b) = sum(gas[a..b]) - sum(cost[a..b]) be the net fuel from a to b. By assumption, T(s, k - 1) ≥ 0 (we made it past k - 1) and T(s, k) < 0 (we failed at k).

Consider any candidate start s' ∈ [s, k]. To complete the lap from s', we need partial sums T(s', i) ≥ 0 for every i between s' and s' + n - 1 (mod n) — in particular, T(s', k) ≥ 0 (assuming s' ≤ k; otherwise we’d be considering s' = k + 1 which is outside the claim’s range).

But T(s', k) = T(s, k) - T(s, s' - 1) ≤ T(s, k) < 0 (since T(s, s' - 1) ≥ 0 by the assumption that we made it past every index in [s, s' - 1]). So starting from s', the tank goes negative at index k, and s' is not a valid start.

Therefore, after a failure at k, we can safely skip all of [s, k] and resume the search from k + 1. QED for the key claim.

Wrapping up. Each index is visited at most once as part of either a successful prefix or the “reset point.” The algorithm runs n iterations. If sum(gas) ≥ sum(cost), the final start is a valid starting point — because the algorithm has effectively eliminated all other candidates, and the problem guarantees a unique solution when one exists. (Formally: from start to the end of the array, no negative event occurred. The wrap-around portion (from index 0 back to start - 1) accumulates at most sum_total - tank_so_far ≤ sum_total = T_total ≥ 0, but we need the running tank non-negative, which follows from the invariant: every prefix from start is non-negative until end, and the wrap-around is the complement, which by total non-negativity stays non-negative.)

The careful formal completion: since T_total ≥ 0, and T(start, n - 1) ≥ 0, we have T(0, start - 1) = T_total - T(start, n - 1) ≤ T_total, but we need positivity of partial sums. The invariant from each reset proved that no earlier candidate works; combined with uniqueness, start is the unique answer.

Complexity

Time O(n) — one pass for sum, one pass for the loop.
Space O(1).

Implementation Requirements

Pre-check sum(gas) < sum(cost) is optional (the algorithm itself returns the right start either way only if a solution exists; the pre-check is cheap and avoids returning a bogus value).
Reset tank = 0 (not tank = gas[i+1] - cost[i+1]) when starting fresh.
start = i + 1 after failure at i.
The variant where you maintain both running and total in a single pass is also acceptable:

def can_complete_circuit_one_pass(gas, cost):
    total = tank = 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

Tests

def test_gas_station():
    assert can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]) == 3
    assert can_complete_circuit([2,3,4], [3,4,3]) == -1
    assert can_complete_circuit([5], [4]) == 0
    assert can_complete_circuit([3,1,1], [1,2,2]) == 0
    assert can_complete_circuit([5,1,2,3,4], [4,4,1,5,1]) == 4
    # exact match (zero margin)
    assert can_complete_circuit([1,2,3], [3,2,1]) in (0, 1, 2)  # one of these
    # all zeros
    assert can_complete_circuit([0,0,0], [0,0,0]) == 0
    # cannot start
    assert can_complete_circuit([1,1,1], [2,2,2]) == -1

Stress-test versus brute force for n ≤ 50.

Follow-up Questions

Find the index where you must idle if the route is infeasible. Slightly different problem; same scan structure.
Multiple cars on the same circuit. Independent problems per car.
Variable tank capacity. Now state is two-dimensional; greedy may fail; revert to DP / simulation.
Two-direction route. Run the greedy in both directions; combine.

Product Extension

Battery-powered EV routing with charging stations of variable wattage and costs. Drone delivery routes with refuel points. Spacecraft trajectory planning with gravity-assist maneuvers (highly idealized).

Language / Runtime Follow-ups

Python: as shown.
Java: identical structure; int total = 0, tank = 0, start = 0;.
Go: total, tank, start := 0, 0, 0.
C++: int total = 0, tank = 0, start = 0;. Watch overflow if gas[i] and cost[i] are at the upper end and n = 10^5: 10^4 * 10^5 = 10^9, within int32 range, but borderline; use long long to be safe.
JS/TS: let total = 0, tank = 0, start = 0;. JS numbers are 64-bit floats, no overflow worry at this scale.

Common Bugs

Resetting tank = gas[i] - cost[i] instead of tank = 0 after failure (you’d be double-counting the failure point).
Setting start = i instead of start = i + 1 after failure.
Forgetting the total < 0 → -1 check, returning a bogus index.
Iterating in the wrong direction or two passes when one suffices.

Debugging Strategy

Print (i, gas[i] - cost[i], tank, start) at each step. The trajectory should show: tank rises and falls, and on each fall below 0 the start jumps to i + 1.
If your output is off by one (returns start - 1 or start + 1), check the assignment in the failure branch.
If you return a start but the route is actually infeasible, you missed the total < 0 gate.

Mastery Criteria

You can write the algorithm in <4 minutes from blank.
You can state the key invariant (“if tank goes negative at k from start s, no station in [s, k] can be a valid start”) in <30 seconds.
You can prove the invariant (using the partial-sum decomposition T(s', k) = T(s, k) - T(s, s' - 1)) in <2 minutes, out loud.
You can articulate why total < 0 → -1 is sufficient and necessary, in <30 seconds.
You can produce the brute-force baseline as a stress-test oracle in <3 minutes when asked.

← Lab 03 — Task Scheduler · Phase 6 README · Lab 05 — Huffman Coding →

LeetCode Interview — Extreme Coding