Gas Station Circular Problem, in depth: finite tanks, every valid start, minimum capacity and live updates

The finite-tank model

With capacity C, arriving at station j with t litres, you fill up to the limit and drive on. The new tank is t' = min(C, t + gas[j]) − cost[j], and the run fails if t' < 0. Fuel above C is spilled. That breaks the totals argument: total gas can exceed total cost and still no start works, because the spill eats the margin. Take gas = [4, 1, 6, 2, 3] and cost = [3, 4, 2, 3, 3]. Total gas is 16 and total cost 15, a margin of one litre. Start 2 is the only valid start without a cap. Here is its tank after each leg:

With C = 5 the car spills one litre at station 2 and another at station 0, and the one-litre margin cannot cover two. No start works at C = 5, even though 16 ≥ 15. So any code that answers the capped problem with the uncapped sum test is wrong.

Why the skip argument survives the cap

It is tempting to conclude that the cap also breaks the skip argument, which lets the classic greedy discard every start it passes through. It does not, and the reason is one property.

Monotonicity. The update t ↦ min(C, t + g) − c never decreases as t increases. Applying it leg after leg preserves order. If two cars drive the same legs and one starts with at least as much fuel, it has at least as much fuel at every later station. So if the richer car runs dry, the poorer one runs dry at the same leg or earlier.

Capped skip lemma. Start at s and suppose the first failure is the leg out of station i. Take any j with s < j ≤ i. The car from s reached j with some tank t_j ≥ 0, because it survived every earlier leg. A car starting at j begins with 0 ≤ t_j and drives the same legs j to i. By monotonicity its tank at i is at most the first car's, which is negative. So every start from s to i fails, and the next candidate is i + 1.

The argument never used additivity. What dies is only the closing claim that the surviving candidate is valid whenever total gas covers total cost. Replace it with verification: keep simulating from the candidate until it completes n legs or fails.

A linear algorithm for any capacity

def first_valid_start(gas, cost, cap):
    """Smallest start that completes the loop with tank capacity cap, or -1."""
    n = len(gas)
    s, tank, i = 0, 0, 0
    while s < n:
        j = i % n
        tank = min(cap, tank + gas[j]) - cost[j]
        if tank < 0:                 # every start in s..i is now ruled out
            s, tank = i + 1, 0
        elif i - s + 1 == n:         # completed n legs from s
            return s
        i += 1
    return -1

A start is returned only after n consecutive legs succeed, and −1 only once the lemma has ruled out every start. Since i only moves forward and stays below s + n, the loop does at most 2n − 1 leg updates. That makes it O(n) time and O(1) space, the same as the classic greedy. Pass cap=float("inf") and it solves the uncapped problem as well, with no special case. Because starts are tried in increasing order and only provably bad ones are skipped, it returns the smallest valid start.

Testing against an oracle

A clever argument deserves a dumb check. The oracle simulates every start in O(n²), and random small cases make disagreements easy to read.

import random

def brute_force(gas, cost, cap):
    n, valid = len(gas), []
    for s in range(n):
        tank = 0
        for k in range(n):
            j = (s + k) % n
            tank = min(cap, tank + gas[j]) - cost[j]
            if tank < 0:
                break
        else:
            valid.append(s)
    return valid

def test(trials=100_000, seed=0):
    rnd = random.Random(seed)
    for _ in range(trials):
        n, cap = rnd.randint(1, 10), rnd.randint(0, 12)
        gas = [rnd.randint(0, 9) for _ in range(n)]
        cost = [rnd.randint(0, 9) for _ in range(n)]
        want = brute_force(gas, cost, cap)
        assert first_valid_start(gas, cost, cap) == (want[0] if want else -1)

Small values make ties, zero-cost legs, legs longer than the tank and exact-zero tanks common, which is where off-by-one errors live. Every function here passed an oracle like this.

Sizing the tank by binary search

Validity is monotone in the capacity too: a bigger tank leaves at least as much fuel after every leg. So the smallest workable tank can be found by binary search. The lower bound is max(cost), since a leg longer than the tank is impossible. The upper bound is max(sum(gas), max(cost)): no tank ever holds more than all the gas on the route, so a cap that large never spills.

def min_capacity(gas, cost):
    """Smallest tank that admits some start, or None if no tank is big enough."""
    lo, hi = max(cost), max(sum(gas), max(cost))
    if first_valid_start(gas, cost, hi) == -1:
        return None
    while lo < hi:
        mid = (lo + hi) // 2
        if first_valid_start(gas, cost, mid) != -1:
            hi = mid
        else:
            lo = mid + 1
    return lo

For the example route this returns 6, matching the table. The cost is O(n log S), where S is the total gas. The same pattern answers questions such as the smallest battery for a delivery loop, or the smallest buffer for a cyclic producer and consumer pipeline.

Every valid start: legs as composable functions

To list every valid start, stop thinking of a leg as an operation and treat it as a value. Each leg is a function of the incoming tank, x ↦ min(A, x + B), defined only when the outgoing tank is non-negative, which means x ≥ L. For one leg, A = C − cost, B = gas − cost and L = cost − gas. If the cost exceeds C the leg is dead and no tank survives it.

Running f and then g gives a map of the same shape. Write f = (L₁, A₁, B₁) and g = (L₂, A₂, B₂). Then g(f(x)) = min(min(A₂, A₁ + B₂), x + B₁ + B₂). The domain needs x ≥ L₁ and f(x) ≥ L₂. Since f is monotone, that is x ≥ L₂ − B₁, possible only if A₁ ≥ L₂. Composition is associative, so a whole loop collapses to one triple. Start s is valid exactly when 0 ≥ L for the composition of legs s through s + n − 1.

INF = float("inf")
IDENTITY = (-INF, INF, 0)        # (L, A, B): x -> min(A, x + B), defined when x >= L
DEAD = (INF, -INF, 0)            # no tank level survives

def leg(gas_i, cost_i, cap):
    if cost_i > cap:
        return DEAD
    return (cost_i - gas_i, cap - cost_i, gas_i - cost_i)

def then(f, g):
    """The map 'do f, then g'."""
    L1, A1, B1 = f
    L2, A2, B2 = g
    if L1 == INF or L2 == INF or A1 < L2:
        return DEAD
    return (max(L1, L2 - B1), min(A2, A1 + B2), B1 + B2)

Each window of n legs over the doubled route is one start. Composition has no inverse, so you cannot subtract the departing leg as with prefix sums. Use a two-stack queue (sliding window aggregation): the back keeps a running composition of the newest legs, the front stores suffix compositions of the oldest, and an empty front is refilled by flipping the back once.

def all_valid_starts(gas, cost, cap):
    """Every start that completes the loop, in O(n) amortised compositions."""
    n = len(gas)
    legs = [leg(gas[i % n], cost[i % n], cap) for i in range(2 * n - 1)]
    front = []                    # front[-1] = composition of the oldest legs in the window
    back, back_agg = [], IDENTITY
    valid = []
    for r, f in enumerate(legs):
        back.append(f)
        back_agg = then(back_agg, f)
        if len(front) + len(back) > n:       # evict the oldest leg
            if not front:                    # flip: rebuild suffix compositions
                agg = IDENTITY
                while back:
                    agg = then(back.pop(), agg)
                    front.append(agg)
                back_agg = IDENTITY
            front.pop()
        if r >= n - 1:
            window = then(front[-1], back_agg) if front else back_agg
            if window[0] <= 0:               # starting empty is allowed
                valid.append(r - n + 1)
    return valid

On gas = [3, 3, 0, 4, 0] with every cost 2, this returns [0, 3] for any C ≥ 4 and nothing for C = 3. Two valid starts are exactly what the single-answer greedy cannot show you. If the car may start with x₀ litres, test x₀ ≥ L instead of 0 ≥ L.

Live updates with a segment tree

When values change between queries, as with charger outages or live traffic, store the leg triples in a segment tree. Each node holds the composition of its range, in order. A point update recomputes O(log n) nodes. To test start s, compose the range s to n − 1 and then 0 to s − 1, which is two O(log n) queries.

class LegTree:
    def __init__(self, gas, cost, cap):
        self.n, self.cap, self.size = len(gas), cap, 1
        while self.size < self.n:
            self.size *= 2
        self.t = [IDENTITY] * (2 * self.size)
        for i in range(self.n):
            self.t[self.size + i] = leg(gas[i], cost[i], cap)
        for v in range(self.size - 1, 0, -1):
            self.t[v] = then(self.t[2 * v], self.t[2 * v + 1])

    def update(self, i, gas_i, cost_i):
        v = self.size + i
        self.t[v] = leg(gas_i, cost_i, self.cap)
        v //= 2
        while v:
            self.t[v] = then(self.t[2 * v], self.t[2 * v + 1])
            v //= 2

    def query(self, lo, hi):
        """Composition of legs lo..hi-1, in order."""
        left, right = IDENTITY, IDENTITY
        lo += self.size; hi += self.size
        while lo < hi:
            if lo & 1:
                left = then(left, self.t[lo]); lo += 1
            if hi & 1:
                hi -= 1; right = then(self.t[hi], right)
            lo //= 2; hi //= 2
        return then(left, right)

    def can_start(self, s):
        return then(self.query(s, self.n), self.query(0, s))[0] <= 0

The query keeps separate left and right accumulators because the composition is not commutative. Folding both sides into one variable is the classic bug when people adapt a sum or min segment tree. For background on the structure itself, see segment trees. The sliding-window technique is a cousin of the monotonic deque in sliding window minimum.

Failure modes

• Using the sum test with a cap. Total gas at least total cost no longer implies a solution. Always verify the candidate.
• Composing in the wrong order. then(f, g) means f first. Swapping the arguments passes most symmetric tests and fails on real routes.
• A wrong identity or dead element. The identity must leave every triple unchanged, and DEAD must absorb everything. Test both explicitly.
• Infinity in fixed-width integers. In C++ or Java, pick sentinels well outside any reachable tank value and guard additions, or the dead-leg check overflows.
• Forgetting legs longer than the tank. These make every start impossible. The leg constructor must catch them, not the main loop.

Trade-offs

What to do next

1. Run the oracle test above against your own implementation before trusting it on real data.
2. Trace the C = 5 row of the worked example by hand and find the two spills.
3. Port then to a typed language with integer sentinels and test identity, DEAD and associativity on random triples.
4. Extend the leg triple with a per-station refuelling limit and check that composition still closes.
5. Review the exchange arguments behind other greedy proofs in greedy algorithms and fractional knapsack.