LeetCode 134 · Medium · Greedy

Gas Station

Stations sit on a loop. Station i gives gas[i] fuel, and driving on to the next one burns cost[i]. Starting with an empty tank, return the one station you can start from to drive the whole loop, or -1 if none works.

O(n)time
O(1)space
restartafter the tank dips below 0

comma-separated integers · 1–8 stations, the same count in both · each 0 to 20 · at most one start may work

public int canCompleteCircuit(int[] gas, int[] cost) { int sumGas = 0; int sumCost = 0; for (int i = 0; i < gas.length; i++) { sumGas += gas[i]; sumCost += cost[i]; } if (sumGas < sumCost) { return -1; } int total = 0; // tank since the current start int res = 0; for (int i = 0; i < gas.length; i++) { total += gas[i] - cost[i]; if (total < 0) { total = 0; res = i + 1; // restart after i } } return res;}
i
—
gas[i] − cost[i]
—
total
—
res
—

Why it works

  1. Brute force simulates the loop from every start: n starts, n stations each, O(n²).
  2. Enough fuel overall means some start works. If sumGas ≥ sumCost, the start right after the lowest point of the running tank never dips below zero. If the sum is short, no start can work: return -1 at once.
  3. A failed run rules out its whole stretch. If the tank from res goes negative at i, then starting at any station between res and i also fails: you would arrive there with a tank ≥ 0 when starting from res, and even that was not enough. So jump straight to i + 1. One pass: O(n) time, O(1) space.
  4. Pitfall: you do not need to wrap around and re-check the stations before res. The total check already guarantees the surplus from the last run covers the deficit of the earlier ones.
  5. Related: the same "drop a negative prefix" reset is Kadane's algorithm in Maximum Subarray (53).