Gas Station: Find the Start of a Circular Route in One Greedy Pass

Problem

Stations are arranged in a circle. Station i provides gas[i] units of fuel, and driving from station i to station i + 1 (wrapping to 0 after the last) uses cost[i] units. You start with an empty tank at a station of your choice, fill up there, and drive clockwise. Return the index of a station from which you can complete the full circle, or -1 if none exists. When a solution exists it is unique.

This is widely known as LeetCode 134, “Gas Station”.

Assume up to 100,000 stations.

Examples

gas  [2, 5, 1, 3]
cost [3, 2, 5, 1]
net  [-1, 3, -4, 2]   total 0, so a start exists
start 3: tank 3 - 1 = 2 -> station 0: 2 + 2 - 3 = 1 -> station 1: 1 + 5 - 2 = 4 -> station 2: 4 + 1 - 5 = 0 -> back to 3
start 1 fails: 5 - 2 = 3, then 3 + 1 - 5 = -1
-> 3

gas [1, 1], cost [2, 1]   -> -1   (total gas 2 is less than total cost 3)
gas [4], cost [4]         -> 0

Approach 1: simulate from every start

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

O(n^2) time.

Approach 2: optimal, one greedy pass

Two facts

1. Feasibility. If the sum of gas[i] - cost[i] is negative, you cannot cover the total distance from anywhere.
2. Skipping. Suppose you start at s and the tank first goes negative after station i. Every station k between s and i was reached with a non-negative tank, so starting at k gives you at most the fuel you had on arrival there, never more. You would fail at i or earlier. So the next possible start is i + 1.

When the total is non-negative, the last candidate survives to the end of the array, and the deficits before it are covered by the surplus after it (the total is the sum of both), so it completes the circle.

Python solution

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

Complexity

O(n) time, O(1) space.

Tests

for fn in (can_complete_circuit, can_complete_brute):
    assert fn([2, 5, 1, 3], [3, 2, 5, 1]) == 3
    assert fn([1, 1], [2, 1]) == -1               # not enough fuel overall
    assert fn([4], [4]) == 0                       # single station, exact
    assert fn([3], [4]) == -1                      # single station, short
    assert fn([0, 0, 5], [1, 1, 1]) == 2           # only the last station works
    assert fn([5, 0, 0], [1, 1, 1]) == 0

import random
random.seed(28)
for _ in range(200):
    n = random.randint(1, 7)
    g = [random.randint(0, 5) for _ in range(n)]
    c = [random.randint(0, 5) for _ in range(n)]
    brute = can_complete_brute(g, c)
    fast = can_complete_circuit(g, c)
    # Uniqueness is only guaranteed by the problem statement; when several starts work,
    # check that the greedy answer is one of them.
    if brute == -1:
        assert fast == -1
    else:
        assert fast != -1 and can_complete_brute(g[fast:] + g[:fast], c[fast:] + c[:fast]) == 0

Edge cases and pitfalls

• Forgetting the total check returns a start even when none works.
• Resetting to i instead of i + 1: station i itself has already been shown to fail.
• Wrap-around simulation is unnecessary in the greedy version; the total check covers the second half of the circle.
• Ties: with zero-net stations, several starts can work; the problem promises uniqueness, but your tests should not assume it.

Where this shows up in data engineering

The same running-balance reasoning appears in capacity checks: if a buffer (a queue, a quota or a budget) receives and spends amounts over a cycle, a negative cumulative balance tells you where the cycle must not start, and the total tells you whether any schedule can work at all.