134. Gas Station — DSA Atlas

134

MediumGreedy AlgorithmsPrefix balance / greedy start selectionGreedy single pass with tank reset

Gas Station

There are n gas stations in a circle. gas[i] is the fuel available at station i and cost[i] is the fuel needed to travel from station i to station i+1 (wrapping around). Starting with an empty tank, return the index of the station from which you can complete the full circuit once in the clockwise direction, or -1 if impossible. If a solution exists it is guaranteed to be unique.

Open official problem prompt ↗

In plain English

Pick the one starting station (if any) from which a car can loop the whole circle without the fuel tank ever dropping below zero.

Picture it like this

Like planning a road trip on a loop of gas stations: if you ever run dry between two stops, it is pointless to blame any station you already passed, so you simply declare the next station your new departure point and try again.

Example

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Why: Starting at station 3 the tank never goes negative and you return to station 3 with fuel to spare.

Constraints

n == gas.length == cost.length1 <= n <= 10^50 <= gas[i], cost[i] <= 10^4If a solution exists, it is unique

Pattern lesson

See the pattern, then code

Greedy single pass with tank reset

↗

Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. If total gas is at least total cost a solution must exist; and whenever the running tank dips below zero somewhere, no station in the segment just traversed can be the start, so the next station becomes the only viable candidate.

New words, made simpleKnow these before the algorithm

net at station i: gas[i] - cost[i], the fuel gained or lost crossing that leg.
tank: Running fuel balance since the current candidate start.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Try every start (brute force)

Too slow at n = 10^5.

Simulate a full loop from each of the n starting stations.

Time O(n^2)Space O(1)

Best choiceGreedy total + reset

Single pass, constant space, provably correct.

Feasible iff total gas >= total cost; find the start as the point right after the last tank shortfall.

Time O(n)Space O(1)

The rule we keep true

Invariant

At any point, tank holds the fuel accumulated from the current candidate start up to station i without ever having gone negative in between; if it does go negative, no station in [start..i] can be the true start.

Why this is correct

Reasoning

If the tank empties while traveling from start to i, then for every station s in that range the partial sum from s to i is also negative (since the sum from start was already negative and start gave the best head start). Hence none of them work, and the first candidate that survives to the end must be valid because the totals guarantee a solution exists.

The algorithm in three movesSay these aloud before coding

1If sum(gas) < sum(cost) return -1 immediately

tank goes negative through stations 0..2 -> start=3

2Sweep stations keeping a running tank of gas[i] - cost[i]

from 3: +3 then +3 (station4) stays >=0

3Whenever the tank goes negative, reset it to 0 and set the candidate start to i + 1

start=3 survives -> answer 3

4Return the candidate start after the sweep

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1-30

2-41

3-52

4-13

5-24

1 · Readsum(gas)=15, sum(cost)=15

2 · AskTotal enough?

3 · Update state15>=15

4 · ResultA solution exists; continue.

Key takeaway

Each cell is gas[i]-cost[i]; the tank recovers only when the start jumps to station 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-3Global feasibility
If total fuel is less than total cost no start can work, so bail out with -1.
2
Lines 4-5Trackers
tank is the running balance; start is the current best candidate station.
3
Lines 6-7Accumulate net fuel
Add gas[i]-cost[i] for the leg leaving station i.
4
Lines 8-10Reset on shortfall
A negative tank disqualifies the whole traversed segment, so the next station becomes the new start and the tank clears.
5
Lines 11Answer
Given a solution exists, the surviving start completes the loop.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single station where gas[0] >= cost[0] returns 0, otherwise -1
Total gas exactly equal to total cost still yields a valid unique start
All stations self-sufficient returns index 0

Common beginner mistakes

Returning the candidate start without first checking global feasibility, which can output a wrong index when no solution exists
Resetting start to i instead of i + 1
Forgetting to zero the tank on reset, corrupting later balances

Check your understanding

Why is it safe to jump the start all the way to i+1 when the tank goes negative at i?

Gas Station

Gas Station

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Greedy Algorithms