Gas Station

Medium#134reset the start

Gas stations stand on a circular road. Station k gives gas[k] units of fuel, and the road from it to the next station takes cost[k]. The car starts at some station with an empty tank. Find the station from which it can drive the whole circle, or return -1 if there is none; if there is one, it is the only one. Our example: gas [4, 3, 1, 5, 2, 4, 1], cost [2, 2, 5, 2, 3, 2, 3] — the answer is 3.

134 Gas StationWalkthrough · 1×

Example: gas [4, 3, 1, 5, 2, 4, 1], cost [2, 2, 5, 2, 3, 2, 3]. gain is what a station adds to the tank after its road; tank is the fuel on leaving each station on the trip from start.

gascostgaintank04−2+213−2+121−5-435−2+342−3-154−2+261−3-2
not reachedon the trip from startstation iruled out as a startthe answer

total sums every station: 0 so far

01/41
restart · back · play · step
Speed
1function canCompleteCircuit(gas, cost):
2 total = 0
3 tank = 0
4 start = 0
5 for i from 0 to len(gas) - 1:
6 gain = gas[i] - cost[i]
7 total = total + gain
8 tank = tank + gain
9 if tank < 0:
10 start = i + 1 // none of start..i works
11 tank = 0
12 return start if total >= 0 else -1
state
total
0
tank
–
start
–
i
–
gain
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. If the car starting at start runs dry right after station i, no station between them works either: it would reach i with only part of the same fuel, and every part before it added ≥ 0. So the next start to try is i + 1, and no station is tried twice.
  2. If total ≥ 0, the circle has enough fuel in all. The trip from the last start to the end never runs dry, and what it has left covers the stretch before start, which lost exactly what the rest gained.
  3. If total < 0, no start can help: the circle burns more than it gives.

Complexity

Time O(n): one pass over the stations, each looked at once. Memory O(1): only total, tank and start. Trying every start would take O(n²).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.