DSA Gas Station

The problem

The gas station problem gives two lists of the same length. The list gas says how much fuel each station gives. The list cost says how much fuel the drive to the next station uses.

A trip starts at one station with an empty tank. The trip visits every station once and returns to its start. The answer is the starting station that completes the trip, or -1 when no start works.

cases = [
    ([1, 2, 3, 4, 5], [3, 4, 5, 1, 2], 3),
    ([5, 1, 2, 3, 4], [4, 4, 1, 5, 1], 4),
    ([2, 3, 4], [3, 4, 3], -1),
    ([3, 1, 1], [1, 2, 2], 0),
]
for gas, cost, expected in cases:
    print("gas", gas, "cost", cost, "-> start:", expected)

Read one row at a time. The first two rows have a working start late in the circle. The third row has less gas than cost in total, so no start can work.

Intuition: the biggest station is not the answer

A first guess picks the station with the most gas. That station feels safest. The guess ignores the costly legs that follow it.

gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
start = 4
tank = 0
for step in range(len(gas)):
    i = (start + step) % len(gas)
    tank += gas[i] - cost[i]
    print("station", i, "tank:", tank)
    if tank < 0:
        print("the trip fails at station", i)
        break

Station 4 holds the most gas, and the trip still fails. The two costly legs after it drain the tank. A working start depends on the whole circle, not on one rich station.

Brute force: try every start

The brute force simulates the whole trip for each start. A simulation stops at the first negative tank. A counter records every leg driven.

def brute(gas, cost):
    visits = 0
    for start in range(len(gas)):
        tank = 0
        ok = True
        for step in range(len(gas)):
            i = (start + step) % len(gas)
            visits += 1
            tank += gas[i] - cost[i]
            if tank < 0:
                ok = False
                break
        if ok:
            return start, visits
    return -1, visits

for gas, cost in [([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]),
                  ([5, 1, 2, 3, 4], [4, 4, 1, 5, 1]),
                  ([2, 3, 4], [3, 4, 3])]:
    start, visits = brute(gas, cost)
    print("gas", gas, "-> start:", start, "legs driven:", visits)

The count stays small here because failing starts die early. A start that almost works drives nearly the whole circle before failing. In the worst case, every start drives many legs.

The optimal solution: one running tank, reset on failure

The state is one running tank and one candidate start. The tank holds the fuel balance since the candidate. A negative tank rules out the candidate and every start between it and the failure point, so the scan restarts once at the next station.

One check comes first. If total gas is below total cost, no start exists. When the totals pass, the surviving candidate is the answer.

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

cases = [
    ([1, 2, 3, 4, 5], [3, 4, 5, 1, 2], 3),
    ([5, 1, 2, 3, 4], [4, 4, 1, 5, 1], 4),
    ([2, 3, 4], [3, 4, 3], -1),
    ([3, 1, 1], [1, 2, 2], 0),
]
for gas, cost, expected in cases:
    result = find_start(gas, cost)
    print("gas", gas, "cost", cost, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass in one pass each. No failed start is ever simulated again. The resets carry all the information the brute force re-derived.

Walkthrough: the first circuit, station by station

The walk uses the first case. The candidate starts at station 0. Each negative tank moves the candidate to the next station and empties the tank.

gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
tank = 0
start = 0
for i in range(len(gas)):
    tank += gas[i] - cost[i]
    print("station", i, "tank:", tank)
    if tank < 0:
        print("  start", start, "fails; restart at", i + 1)
        start = i + 1
        tank = 0
print("answer start:", start)

Starts 0, 1 and 2 each fail at their own first leg. Start 3 survives stations 3 and 4. The totals check already promised that the survivor completes the wrap-around legs too.

Complexity

The one-pass solution visits each station once, so its time is O(n) for n stations. It stores two numbers, so its extra space is O(1).

The brute force can drive up to n legs for each of n starts. Its worst-case leg count is n times n.

for n in [5, 10, 20]:
    print("stations", n, "- brute legs up to:", n * n, " one-pass legs:", n)

At 20 stations the gap is 400 legs against 20. The one pass wins by never re-driving a leg for a new candidate.

Edge cases and pitfalls

A single station answers the whole question by itself. Its gas either covers its cost or does not. Equal totals across the circle still guarantee a start, because the final surplus is zero, not negative.

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

print("one station, enough gas:", find_start([5], [3]))
print("one station, short:", find_start([2], [3]))
print("totals short:", find_start([2, 3, 4], [3, 4, 3]))
print("start at the last station:", find_start([1, 2], [2, 1]))
print("start survives from station 0:", find_start([3, 1, 1], [1, 2, 2]))
print("all zeros:", find_start([0, 0], [0, 0]))

The last-station row is the common pitfall in reverse. A scan that gives up when the candidate reaches the final station misses it. The reset rule sets the candidate to the next index without judging it early.