GreedyGreedy

Gas Station Circuit

Find the unique start on a circular route from which a car can complete the loop, in one pass: whenever the running tank goes negative, restart from the next station.

Learn Gas Station (Circular Tour) →
a
-2
0
-2
1
-2
2
3
3
3
4
gas
1
0
2
1
3
2
4
3
5
4
cost
3
0
4
1
5
2
1
3
2
4
tank
·
0
·
1
·
2
·
3
·
4
1/135 stations arranged in a circle. The top row is the net gain at each station, gas[i] - cost[i]: a positive station leaves you with fuel to spare, a negative one drains the tank. The question is whether some starting station lets you get all the way around without the tank ever dropping below zero.
Current candidate startStation being driven throughEliminated as a startThe valid start
PseudocodeLearn Gas Station (Circular Tour) →
1total = 0, tank = 0, start = 0
2for i in 0 .. n-1:
3  gain = gas[i] - cost[i]
4  total += gain; tank += gain
5  if tank < 0:                      # cannot reach station i+1 from `start`
6    start = i + 1                   # ...and no station in start..i works either
7    tank = 0
8return total >= 0 ? start : -1
Variables
stations5
totalGas15
totalCost15
surplus0
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed