GreedyAlgorithmaka circular tour, petrol pump problem, minimum starting index

Gas Station (Circular Tour)

Find the unique start on a circular route from which a car can complete the loop, in one pass: whenever the running tank goes negative, restart from the next station.

Pattern: Prefix Sum Practice (3)

Progress

Overview

There are n stations on a circle; station i provides gas[i] fuel and driving to station i+1 costs cost[i]. Starting with an empty tank, find a start index from which the car can complete the full circle, or return −1. A solution exists iff Σ gas ≥ Σ cost, and when it does, it is unique.

The greedy: track tank as the running sum of gas[i] − cost[i] from the current candidate start. If tank drops below zero at station i, no start in [start, i] can work, so set start = i + 1 and tank = 0. After one pass, start is the answer if total ≥ 0.

greedycircular arrayprefix sumone passinvariant

Intuition

A mental model before the formal terms.

Imagine driving and watching the fuel gauge. If you run dry between stations 3 and 4, starting anywhere between your original start and station 3 would only have been worse — you would have arrived at every one of those stations with less fuel than you did now (you got there with a non-negative tank plus whatever you started with). So the only hope is to start after the breakdown point.

Once the total gas covers the total cost, some prefix of the loop has the lowest running balance; starting right after that lowest point means every subsequent balance is measured from the bottom, so it never dips below zero.

How it works

Initialize total = 0, tank = 0, start = 0.
For each i: diff = gas[i] − cost[i]; add to both total and tank.
If tank < 0: set start = i + 1, tank = 0 — every start in [start, i] fails.
After the loop, return start if total ≥ 0, else −1.

Why it works

Greedy-choice property (skip lemma). Suppose starting at s the tank first goes negative when leaving station i. For any s < k ≤ i, the tank on arrival at k from s was ≥ 0, so the fuel available at k when starting from s is at least the fuel available when starting from k itself (which is 0). Hence starting at k reaches every station up to i with no more fuel than starting at s did, and also fails at i. All of s..i are eliminated at once — jumping to i + 1 skips nothing viable.

Sufficiency of `total ≥ 0`. Let P_j = Σ_{t<j} (gas[t] − cost[t]) be prefix balances and m the index of the minimum prefix. Starting at m, the balance after any number of steps is P_j − P_m ≥ 0 for j > m, and after wrapping, total + P_j − P_m ≥ 0 because total ≥ 0. So the circuit completes. The one-pass greedy ends exactly at that start, because it resets precisely when a new prefix minimum is reached.

Uniqueness: if total ≥ 0, the start found is the last reset; any earlier start was eliminated by the skip lemma and any later start is not reachable as a reset point.

Recognition

How to tell a problem wants this.

Circular route, per-station gain and per-segment cost, "can you complete the circuit / from where".
A running balance that must never go negative over a cyclic sequence — the problem is really "rotate the array so all prefix sums are non-negative".
Constraints guaranteeing a unique answer are a tell that the greedy reset works.

“sum of subarray” → Prefix Sum “maximum number of non-overlapping” → Greedy

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1total = tank = 0; start = 0
2for i in 0..n-1:
3  diff = gas[i] - cost[i]
4  total += diff; tank += diff
5  if tank < 0: start = i + 1; tank = 0
6return start if total >= 0 else -1

Implementations

1# Circular tour: gas[i] is the fuel at station i, cost[i] the fuel needed to
2# reach station i+1. Find a start from which the tank never goes negative.
3# One pass, no simulation of every candidate.
4 
5 
61 · If total gas < total cost, no start can work — that check is separate
7# from finding WHICH start works
8def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
9    if not gas:
10        return -1  # no stations, so no valid start index exists
11    total = tank = 0
12    start = 0
13 
14    for i, (g, c) in enumerate(zip(gas, cost)):
15        gain = g - c
16        total += gain
17        tank += gain
182 · A negative tank means no station in [start, i] can be the answer
19        if tank < 0:
20            start = i + 1
21            tank = 0
22 
233 · Feasibility is decided by the total, not by the last surviving start
24    return start if total >= 0 else -1
25 
26 
274 · Why skipping the whole prefix is safe: if the tank goes negative first
28# at station i starting from s, then every station between s and i also fails
29# before reaching i, because each of those starts has a smaller running sum.
30def verify_circuit(gas: list[int], cost: list[int], start: int) -> bool:
31    n = len(gas)
32    if start < 0:
33        return False
34    tank = 0
35    for k in range(n):
36        i = (start + k) % n
37        tank += gas[i] - cost[i]
38        if tank < 0:
39            return False
40    return True
41 
42 
435 · The brute-force version, O(n^2), kept for comparison and testing
44def can_complete_circuit_brute(gas: list[int], cost: list[int]) -> int:
45    for s in range(len(gas)):
46        if verify_circuit(gas, cost, s):
47            return s
48    return -1

Walkthrough

for i, (g, c) in enumerate(zip(gas, cost)) walks index and both values together, which reads as the problem statement.
total = tank = 0 chains the initialisation of two independent accumulators.
The reset start = i + 1; tank = 0 discards the failed prefix; total is deliberately not reset.
return start if total >= 0 else -1 puts the feasibility decision in one expression.
Python integers are unbounded, so neither accumulator can overflow regardless of route length.

Complexity (this implementation)

time O(n) for the greedy, O(n^2) for the brute force · space O(1)

Language notes

zip truncates to the shorter list silently; zip(gas, cost, strict=True) (3.10+) raises on a length mismatch, which is the safer spelling here.
% returns a non-negative result for a positive modulus, so (start + k) % n is safe even for a negative start — unlike C++ and JavaScript.
Arbitrary-precision integers remove the overflow concern entirely.
itertools.accumulate(g - c for g, c in zip(gas, cost)) gives the prefix sums directly if a different formulation is wanted.

Common mistakes in this language

Using plain zip on mismatched lists and silently ignoring the tail.
Resetting total along with tank, which breaks the feasibility test.
Returning start without checking total.

Language differences that matter here

Modulo sign matters for the wraparound: Python % is always non-negative for a positive modulus, so (start + k) % n is safe even for a negative start; C++ and JS/TS would produce a negative index.
Overflow: Python is unbounded, C++ needs long long accumulators, and JS/TS are exact to 2^53.
Pairing two parallel arrays is unchecked in all four, but Python offers zip(..., strict=True) to catch a length mismatch at runtime — the only built-in guard among them.
The -1 sentinel is conventional everywhere; only TypeScript could express number | null without breaking a widely known contract.

Complexity

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

Single pass; no second lap needed because the total check certifies the wrap-around.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Circular arrays where a running balance must stay non-negative and you need the starting rotation.
Feasibility of a cyclic sequence of gains/costs with a single global resource.

Avoid it when

The tank has a capacity cap: gas = [5, 0, 0], cost = [1, 1, 1], capacity 2. Total 5 ≥ 3 and the greedy returns 0, but with a 2-unit tank you run dry before station 2 — the surplus argument assumes fuel carries over unbounded. Simulate with the cap instead.
You need all valid starts or the start minimizing something else (e.g. minimum initial fuel to buy) — compute prefix sums and use the minimum-prefix argument directly.
Non-circular version with variable refuel amounts and a limited number of stops (Minimum Refueling Stops) — that is a max-heap greedy or DP, not this reset trick.

Alternatives

Prefix Sum Kadane's Algorithm Sliding Window (Variable Size)

Common mistakes

Resetting start but forgetting to reset tank (or vice versa).
Running two laps or an O(n²) simulation from every start — the single pass with the total check is enough.
Returning start without checking total ≥ 0; start can be n (out of range) when no solution exists.
Using tank <= 0 as the reset condition — a tank of exactly 0 on arrival is fine.

Interview patterns

Gas Station (LeetCode 134) — be ready to prove the skip lemma.
Minimum-prefix rotation: "rotate so all prefix sums are non-negative" (same idea via Prefix Sum).
Contrast with Kadane's Algorithm: both are one-pass resets when the running value goes negative.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Recognizing a sliding-window problemIntermediate
Prefix sum or segment tree?Intermediate

Mock interviews

Example problems

Maximum Subarraymedium Gas Stationmedium Jump Gamemedium