DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Gas Station

mediumGreedy Must-do

Problem statement

There are n gas stations on a circular road. At station i you can pick up gas[i] units of fuel, and driving from station i to station i + 1 (with the last station leading back to station 0) uses cost[i] units. Your car's tank has no size limit and starts empty.

Return the index of the station where you can start and drive the full loop once in the forward direction without running out of fuel. If no station works, return -1. When an answer exists, it is unique.

Examples

Example 1

Input: gas = [2, 3, 4, 1], cost = [3, 1, 2, 3]

Output: 1

Explanation: Starting at 1 the tank goes 3 - 1 = 2, then 2 + 4 - 2 = 4, then 4 + 1 - 3 = 2, then 2 + 2 - 3 = 1. Starting at 0 or 3 fails on the first leg; starting at 2 runs dry on the leg from 3 to 0.

Example 2

Input: gas = [1, 2, 1], cost = [2, 2, 2]

Output: -1

Explanation: The loop needs 6 units of fuel but only 4 are available in total.

Hints

Approach

One pass with two running sums.

  1. total accumulates gas[i] - cost[i] over the whole loop. tank does the same but resets whenever it goes negative. start = 0.
  2. At each station, add the difference to both. If tank < 0, the current candidate cannot get past station i, so set start = i + 1 and tank = 0.
  3. At the end, return start if total >= 0, else -1.

Two facts make this work. If you start at s and first run dry reaching i + 1, then every station between s and i also fails, because you arrived at each of them with a non-negative tank and still ran dry; starting there with an empty tank is no better. And if the total is non-negative, the last candidate standing must succeed, because the deficit from the part of the loop before it is covered by the surplus it builds up.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
total = tank = start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0: # nothing from start..i can work
start = i + 1
tank = 0
return start if total >= 0 else -1

Follow-up questions

  • The tank has a maximum capacity. Does the greedy still work?
  • Return every station that would work if uniqueness were not guaranteed.

Frequently asked questions

Yes. Look at the running sum of gas[i] - cost[i] around the loop. Start just after the point where that running sum is lowest; from there every partial sum is at least as high as the minimum, so the tank never goes negative. The one-pass algorithm lands on exactly that station.

The "reset when the running balance goes negative" trick is useful for budget and capacity questions over a cycle: which hour of a daily traffic pattern should a batch job start so its buffer never runs out, or where does a rotation have to begin so a shared quota never goes negative.