4.26.4 — Gas Station

LeetCode 134 · Medium

The problem

Stations are arranged in a circle. At station i you gain gas[i] fuel, and driving to station i+1 costs cost[i]. Starting with an empty tank, return the index you must start from to complete the loop, or -1 if it is impossible. The answer is guaranteed unique if it exists.

gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]      →  3

gas  = [2,3,4]
cost = [3,4,3]          →  -1

The pattern

Work with the net gain at each station, gas[i] - cost[i]. Now the question is: from which starting point can you go all the way round without the running total ever dropping below zero?

Two facts do all the work, and both need proving.

Fact 1 — a solution exists exactly when the total net gain is non-negative.

If the total is negative, you burn more fuel than you collect over a full loop, so no start can work. If it is non-negative, a valid start is guaranteed to exist. The first direction is obvious; the second falls out of Fact 2.

Fact 2 — if you run out of fuel travelling from start to i, then no station between them works either.

This is the fact that makes the algorithm one pass, so it is worth proving. Suppose you start at start and fail on the way to station i. Take any station j strictly between them. You arrived at j with a non-negative tank — otherwise you would have failed earlier than i. Starting at j instead means arriving at each later station with less fuel than before. So you fail at i too, or sooner.

So the whole stretch from start to i can be skipped in one step. Every index is tested at most once, and the scan is linear.

The solution

Python

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1                        # not enough fuel in total

        start = 0
        tank = 0

        for i in range(len(gas)):
            tank += gas[i] - cost[i]

            if tank < 0:                     # cannot reach station i+1
                start = i + 1                # skip the whole stretch
                tank = 0                     # start fresh from there

        return start

TypeScript

function canCompleteCircuit(gas: number[], cost: number[]): number {
  const total = gas.reduce((a, b) => a + b, 0) - cost.reduce((a, b) => a + b, 0);
  if (total < 0) return -1;

  let start = 0, tank = 0;

  for (let i = 0; i < gas.length; i++) {
    tank += gas[i] - cost[i];
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }

  return start;
}

No wraparound is needed anywhere. That looks wrong for a circular problem, and it is not.

Once the total check has passed, a valid start exists. The scan finds the last position from which the tank never goes negative through to the end of the array. Because the overall total is non-negative, the fuel accumulated across the skipped prefix is enough to cover the wrap. So the remaining stretch plus the wrap succeeds, and there is nothing to simulate.

tank resets to 0 on failure, because you are now considering a fresh journey beginning at i + 1.

The uniqueness guarantee is what lets the code return the first candidate it finds without checking whether an earlier one also works.

Trace

gas = [1,2,3,4,5], cost = [3,4,5,1,2]. Net: [-2,-2,-2,3,3]. Total is 0, so a solution exists.

i	net	tank	action
0	−2	−2	negative → start = 1, tank 0
1	−2	−2	negative → start = 2, tank 0
2	−2	−2	negative → start = 3, tank 0
3	+3	3	fine
4	+3	6	fine

Answer 3 ✓. Starting at 3: tank 3, then 6, then wrapping through the three negative stations 6 − 2 − 2 − 2 = 0, arriving back exactly empty.

Complexity

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

The brute force tries every start and simulates a full loop — O(n^2). Fact 2 is what removes the outer loop.

Where this goes next

• Maximum Subarray — the same "reset when the running total goes negative" rule, and the same exchange argument behind it. 4.26.1.
• Maximum Sum Circular Subarray — circular again, handled by splitting into wrapping and non-wrapping cases.
• Candy — another greedy that needs two passes and a proof.

The transferable idea: when a failed attempt rules out a whole range of alternatives, the outer loop disappears. That is the same reasoning as the run-start guard in 4.4.9 and the discard proofs in 4.5.

What the interviewer will push on

"Why does a non-negative total guarantee a solution?" Because of Fact 2 — the scan always terminates at a start whose remaining stretch works, and the total guarantees the wrap is covered.

"Why can you skip the whole stretch after a failure?" The proof above: any intermediate station is reached with a non-negative tank, so starting there gives you no more fuel at any later point.

"Why is there no wraparound in the code?" The total check has already accounted for it.

"What if the answer were not unique?" The code returns the first valid start it finds, which is still a correct answer. If you needed all of them, you would collect every candidate and verify each — O(n^2) worst case.

"What is the brute force?" O(n^2), and Fact 2 is what kills the outer loop.

One thing to volunteer: give Fact 2 with its proof before writing the code. This problem is short but almost impossible to justify without it, and an unjustified greedy is a guess.

Next: 4.26.5 Hand of Straights — a greedy where the only decision is which card to start from.