M.A.T.R.I.X

Appearance

Volume ITechnology

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.

Restating the Problem: You have a car that starts with zero fuel. You must pick a starting station on a circular route. At each station, you pump gas[i] into your tank, and driving to the next station consumes cost[i]. You must complete the circle without your fuel ever dropping below 0.

  • Constraints to note: The arrays gas and cost have the same length N, which can be up to 10^5. This implies we need an O(N) algorithm.
  • Edge cases: The net gas might be exactly zero at the end; this is a valid trip, provided you don't drop below zero midway.
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
ts
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.

Code Walkthrough:

  • Initial Viability Check (sum(gas) < sum(cost)): We immediately rule out impossible cases. If the total gas available across all stations is less than the total cost to travel, no starting point can possibly work.
  • Iteration: We loop through each station i. We track our current tank level and our proposed start index.
  • Accumulate Fuel: At each step, we add the net gain (gas[i] - cost[i]) to our tank.
  • Handling Failure (tank < 0): If the tank drops below zero, it means we cannot reach station i+1 from our current start. Due to Fact 2, we know no station between start and i could have worked either. So, we make i+1 our new proposed start and reset tank to 0.
  • Return: If we finish the loop, start holds the correct answer (guaranteed by the initial sum check).

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.

inettankaction
0−2−2negative → start = 1, tank 0
1−2−2negative → start = 2, tank 0
2−2−2negative → start = 3, tank 0
3+33fine
4+36fine

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.

  • Time Complexity: O(n). We calculate the total sum once, and then iterate through the array once. At each station, we do a constant amount of math.
  • Space Complexity: O(1). We only track two variables, start and tank, using no extra data structures.

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.