{ }SolveLogs
⌕
Home / Greedy / #134
LeetCode #134 Medium

Gas Station

Gas Station is LeetCode 134 (Medium). There are n gas stations on a circular route. Station i gives gas[i] fuel, and driving from station i to the next one costs cost[i]. Starting with an empty tank, return the index of the station from which you can drive all the way around once, clockwise, or -1 if no start works.

  • If an answer exists, it is unique.
  • n is up to 10⁵, so trying every start (O(n²)) is too slow; the target is one pass.
Constraints
  • n == gas.length == cost.length
  • 1 <= n <= 10⁵
  • 0 <= gas[i], cost[i] <= 10⁴
  • The input is generated such that the answer is unique.
arraygreedysimulation
Open on LeetCode ↗
02

Intuition

The gas station problem gets simple once you work with each station's gain, gas[i] - cost[i]. Two facts then give a one-pass greedy answer:

  • Total: if all the gains add up to less than 0, the lap needs more fuel than exists, so no start works.
  • Skip: if you start at s and the tank first goes negative at station i, no station from s to i can be the start either. You reached each of them with 0 or more fuel, so starting there instead can only arrive at i with less.

So drive once along the array and restart just past every failure. If the total is not negative, the last restart is the answer.

How to spot this pattern

A circular route with gains and costs, where you need a start whose running sum never drops below zero, is the gas station greedy: a failed run rules out every start inside it. Kadane's algorithm for Maximum Subarray uses the same move of dropping a negative prefix and starting fresh.

03

Approach

Try it first

Before reading on: with gas = [1,2,3,4,5] and cost = [3,4,5,1,2], write the gain at each station. If a start fails at station 2, could any station before 2 have been the answer?

1

Keep two sums

total adds every gain and is never reset; it only decides whether any answer exists. tank is the fuel since the current candidate start, and resets when that candidate fails. Keep them apart: they answer different questions.

2

Add each station's gain

For each station, compute gain = gas[i] - cost[i] and add it to both sums. While tank stays 0 or more, the car from start can reach the next station, so the candidate survives. A tank of exactly 0 is fine: the car arrives empty.

3

Restart after a failure

If tank < 0, the car from start cannot get past station i. Every station between start and i would arrive with even less fuel, so skip all of them at once: set start = i + 1 and tank = 0.

4

Return the candidate

After one pass, if total < 0, return -1. Otherwise return start. The car from start reached the end of the array, and because the total is not negative, the fuel it carries covers the stations before start on the way back round.

04

Gas Station solution in Python | C++ | Java

▶1class Solution:
▶2 def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
▶3 total = tank = start = 0
▶4 for i in range(len(gas)):
▶5 gain = gas[i] - cost[i]
▶6 total += gain
▶7 tank += gain
▶8 if tank < 0:
▶9 start = i + 1
▶10 tank = 0
▶11 return start if total >= 0 else -1
gascostgaintank13−2024−2135−2241+3352+34↑ starttotal0sum of every gain so farstart = 0, tank = 0, total = 0
start0candidate
tank0
total0
Start. Each station's gain is its gas minus the cost to reach the next one. tank follows the car from the current candidate start; total adds every gain and is never reset.
gascostgaintank13−20−224−2135−2241+3352+34↑ starttotal−2sum of every gain so farstation 0: tank 0 − 2 = −2 < 0
gain-21 − 3
tank-2since start 0
total-2
The tank drops to −2: starting from station 0, the car cannot get past station 0.
gascostgaintank13−20−224−2135−2241+3352+34↑ starttotal−2sum of every gain so farstation 0 ruled out → start = 1
start1next candidate
tank0reset
total-2kept
Station 0 fails on its own gain, so it cannot be the start. Restart at station 1 with an empty tank; total keeps counting.
gascostgaintank13−20−224−21−235−2241+3352+34↑ starttotal−4sum of every gain so farstation 1: tank 0 − 2 = −2 < 0
gain-22 − 4
tank-2since start 1
total-4
The tank drops to −2: starting from station 1, the car cannot get past station 1.
gascostgaintank13−20−224−21−235−2241+3352+34↑ starttotal−4sum of every gain so farstation 1 ruled out → start = 2
start2next candidate
tank0reset
total-4kept
Station 1 fails on its own gain, so it cannot be the start. Restart at station 2 with an empty tank; total keeps counting.
gascostgaintank13−20−224−21−235−22−241+3352+34↑ starttotal−6sum of every gain so farstation 2: tank 0 − 2 = −2 < 0
gain-23 − 5
tank-2since start 2
total-6
The tank drops to −2: starting from station 2, the car cannot get past station 2.
gascostgaintank13−20−224−21−235−22−241+3352+34↑ starttotal−6sum of every gain so farstation 2 ruled out → start = 3
start3next candidate
tank0reset
total-6kept
Station 2 fails on its own gain, so it cannot be the start. Restart at station 3 with an empty tank; total keeps counting.
gascostgaintank13−20−224−21−235−22−241+33352+34↑ starttotal−3sum of every gain so farstation 3: tank 0 + 3 = 3
gain34 − 1
tank3since start 3
total-3
The tank is 3, not negative, so the car from station 3 reaches station 4. The candidate survives.
gascostgaintank13−20−224−21−235−22−241+33352+346↑ starttotal0sum of every gain so farstation 4: tank 3 + 3 = 6
gain35 − 2
tank6since start 3
total0
The tank is 6, not negative, so the car from station 3 reaches station 0. The candidate survives.
gascostgaintank13−20−224−21−235−22−241+33352+346↑ starttotal0sum of every gain so fartotal 0 ≥ 0 → return 3
total0
answer3
Answer 3. The car from station 3 made it to the end of the array. The total is 0, not negative, so the fuel it carries is enough to cover the stations before 3 on the way back round.
05

Common pitfalls

Returning start without checking the total

✗ Wrong
return start
✓ Right
return start if total >= 0 else -1

For gas = [2, 3, 4], cost = [3, 4, 3] the scan ends with start = 2, but the gains add up to −1, so no start can finish the lap and the answer is −1.

Restarting at the failing station

✗ Wrong
start = i
✓ Right
start = i + 1

The tank turns negative at station i only if station i's own gain is negative, so starting there fails straight away. The next real candidate is the station after it.

Moving start but keeping the old tank

✗ Wrong
if tank < 0:
    start = i + 1
✓ Right
if tank < 0:
    start = i + 1
    tank = 0

The negative tank belongs to the old candidate. Carrying it over makes the new start look worse than it is, so the scan can skip past the real answer.

06

Edge cases

Gains add up to exactly 0, e.g. gas = [1,2,3,4,5], cost = [3,4,5,1,2]

The car finishes the lap with an empty tank, which still counts. Test total >= 0, not total > 0; the answer here is 3.

07

Complexity

Time
O(n)
Space
O(1)
One pass with three variables. Simulating a full lap from every station is O(n²).
08

Gas Station FAQ

Can you solve the gas station LeetCode problem by trying every start?

Yes: from each station, simulate the lap and stop when the tank goes negative. That is O(n²), up to 10¹⁰ steps for 10⁵ stations, which times out. The greedy pass skips every failed start at once and runs in O(n).

← Prev · #133
Clone Graph
Next · #135 →
Candy