Gas Station: Explaining the Greedy Proof in a Coding Interview

The Gas Station problem (can you drive around a circular route given gas[i] and cost[i]?) is short to code, but interviewers mostly grade whether you can justify the greedy step.

Brute force first

Try every starting station and simulate the loop: O(n^2). Say it, then improve it.

Two facts that give O(n)

  1. If total gas is less than total cost, no start works. Return -1.
  2. If you start at station s and run out of gas before reaching station j, then no station between s and j can be a valid start either. Each of those stations was reached with a non-negative tank, so starting there with an empty tank can only be worse.

So when the tank goes negative at j, jump the candidate start to j + 1 and reset the tank.

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 = i + 1
            tank = 0
    return start

Why the answer is unique and correct

If the totals are non-negative, a solution exists, and the last reset point is the only place from which the tank never dips below zero through the end of the array; the surplus from the total covers the wrap-around part.

Complexity

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

Interview tip

State fact 2 out loud before coding. It turns "I just reset when negative" into a proof the interviewer can follow.

If you want to rehearse explaining proofs like this under time pressure, Linkjob AI coding interview copilot can help. Disclosure: I work on Linkjob AI.

Further reading: Linkjob AI resource directory