intermediate9 min read·Updated October 9, 2026

Gas Station Circular Tour Explained: Tracing gas=[1,2,3,4,5]

Master the greedy circular tour algorithm by tracing gas=[1,2,3,4,5] and cost=[3,4,5,1,2]. Build a mental model for O(n) route validation and edge cases.

By Learnisim AI·Published October 9, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic array indexing
  • Greedy algorithm intuition
  • Modular arithmetic
Circular Gas Station Tour: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Start Index Index: 3 (Valid Circuit) St 0 +1|-3 St 1 +2|-4 St 2 +3|-5 St 3 +4|-1 St 4 +5|-2 O(N) Greedy Ledger Trace (Start at index 3) At Station 3 Gain +4, Cost 1 Tank: 3 At Station 4 Gain +5, Cost 2 Tank: 6 Loop 0, 1, 2 Survives all dips Complete Loop! • Total Gas: 1+2+3+4+5 = 15 • Total Cost: 3+4+5+1+2 = 15 (Sum Gas ≥ Sum Cost) • If tank drops below 0 at station i, start = i + 1. Why Brute Force Fails • Testing every start index takes O(N²) quadratic time. • Restarts throw away valuable terrain data when fuel hits < 0. Greedy single-pass runs in O(N). The Greedy Insight • If total gas < total cost, return -1 (impossible). • Any station between start and failure cannot be the start. Advance start pointer directly. Battery & Route Patterns • Electric vehicle power grids • Circular delivery drone loops • Ring buffer capacity checks Single-pass running ledger Solves cyclic resource limits.
gas=[1,2,3,4,5] cost=[3,4,5,1,2] overview diagram
Why

Why the Circular Gas Station Tour Problem Beats Brute Force

Phase 1: The Circular Drive Dilemma

Imagine you are planning a trip along a circular route with 5 gas stations. You start with an empty tank of gas at station 0. At each station , you collect gas[i] amount of fuel, and then you spend cost[i] amount of fuel to drive to the next station .
For our locked example, the values are gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. If you attempt to solve this by brute force, you might try starting at station 0, simulating every single step until you either run out of fuel or complete the full loop. If station 0 fails, you reset, drive around from station 1, simulate the entire tour again, and repeat the process for all stations.
As the number of stations grows into the thousands, checking every possible starting index one by one leads to a quadratic time complexity. When your tank hits negative fuel halfway through a trial, starting over from scratch discards valuable information about the terrain you just traversed.
Why the Circular Gas Station Tour Beats Brute Force gas = [1,2,3,4,5] | cost = [3,4,5,1,2] — Starting at 0 fails at 2, skipping ahead instantly! St 0 +1 / -3 St 1 Skip St 2 Fail (-2) St 3 Success! St 4 +5 / -2 O(N) Scan Jump to St 3 × Brute Force Approach O(N²) • Try starting at Station 0: simulates full loop, fails at Station 2. • Reset tank, restart completely from Station 1, simulate again. • Redundant work! Discards terrain insight when fuel hits negative. Result: Slow, checks every index from scratch (Quadratic time). ✓ Linear Greedy Insight O(N) • Accumulate total deficit (surplus < 0); track current tank. • Core Rule: If trip fails at St 2, NO station between 0 & 2 can start! • Instantly shift start candidate to Station 3 without resetting. Result: Single pass O(N) time, zero redundant simulation.
Why the Circular Gas Station Tour Problem Beats Brute Force diagram
Model

The Circular Tour Model: Gas, Cost, and Tank States

Phase 2: The Mental Model

To formalize our locked working example, and , we need to stop thinking about a fleet of cars and start thinking about a single running fuel ledger. Imagine driving a single vehicle around the ring of 5 stations, where at each station :
1. You collect into your tank.
2. You burn traveling from to .
If you start at station 0, you collect 1 unit and spend 3, leaving your tank at . Because your tank dips below zero, you immediately realize that every station from 0 up to is invalid as a starting point. Why? If you couldn't even make it from 0 to 1, starting at 1 with an empty tank would only give you even less accumulated momentum than starting at 0 did.
Instead of simulating every single starting index from scratch ( time), our model tracks two metrics simultaneously as we make a single pass: the running tank balance and the total surplus across the entire route. When the running tank drops below zero at station , we know our candidate start index is flawed. We reset our candidate start to , dump the negative tank balance back to 0, and continue our sweep.
Try this: Given gas=[1,2,3,4,5] and cost=[3,4,5,1,2], trace what happens to your running tank when you attempt to start at index 0 versus index 3.
The Circular Tour Model: Gas, Cost, and Tank States Working Example: gas=[1, 2, 3, 4, 5], cost=[3, 4, 5, 1, 2] Station Ring (0 to 4) 0 g1,c3 (-2) 1 g2,c4 2 g3,c5 3★ g4,c1 (+3) 4 g5,c2 Station Delta Breakdown (gas[i] - cost[i]) Idx Gas Cost Net (G-C) Running Tank 0 1 3 -2 -2 (FAIL) 1 2 4 -2 -4 (Reset start) 2 3 5 -2 -6 (Reset start) 3 4 1 +3 +3 (New Start) 4 5 2 +3 +6 (Surplus!) Core Mechanics & Invariants for O(N) Linear Scan 1. Feasibility Check Sum(Gas) = 15, Sum(Cost) = 15 Total Gas >= Total Cost (Valid!) 2. Tank Dips Below Zero At i=0, tank drops to -2 (< 0) Invalidates 0, 1, and 2 as starts 3. Greedy Candidate Shift Reset start to i+1 (Station 3) Completes full circuit safely!
The Circular Tour Model: Gas, Cost, and Tank States diagram
Worked example

Tracing the Circular Gas Station Tour Step-by-Step

Phase 3: Worked Example

To see how the accumulator algorithm bypasses simulation, let us run our exact problem instance from start to finish. We are given five stations around a circular track:
* gas = [1, 2, 3, 4, 5]
* cost = [3, 4, 5, 1, 2]
We maintain three tracking variables: total (net surplus across the entire trip), tank (current fuel reserve since our last trial start), and start (candidate starting index).
Given / Setup:
* total = 0, tank = 0, start = 0
Steps / Trace:
Let us iterate through each station index from 0 to 4:
1. : Station 0 has gas[0] = 1, cost[0] = 3.
* Net change: .
* total = 0 + (-2) = -2
* tank = 0 + (-2) = -2
* Since tank < 0, our attempt starting at index 0 failed. We reset start = i + 1 = 1 and reset tank = 0.
2. : Station 1 has gas[1] = 2, cost[1] = 4.
* Net change: .
* total = -2 + (-2) = -4
* tank = 0 + (-2) = -2
* Since tank < 0, we reset start = i + 1 = 2 and reset tank = 0.
3. : Station 2 has gas[2] = 3, cost[2] = 5.
* Net change: .
* total = -4 + (-2) = -6
* tank = 0 + (-2) = -2
* Since tank < 0, we reset start = i + 1 = 3 and reset tank = 0.
4. : Station 3 has gas[3] = 4, cost[3] = 1.
* Net change: .
* total = -6 + 3 = -3
* tank = 0 + 3 = 3
* tank >= 0, so we successfully reach the next station.
5. : Station 4 has gas[4] = 5, cost[4] = 2.
* Net change: .
* total = -3 + 3 = 0
* tank = 3 + 3 = 6
* tank >= 0, completing our loop check.
Result:
At the end of the loop, our global total is 0 (which is not ), meaning a valid complete tour exists. We return the final candidate start = 3.
Try this: Given gas = [1,2,3,4,5] and cost = [3,4,5,1,2], trace the exact values of total and tank at the end of i = 3.
Phase 3 Worked Example: Tracing Stations i = 0 to 3 gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] | tank < 0 triggers reset of start & tank i = 0 (Fail) gas: 1 | cost: 3 Net: 1 - 3 = -2 tank: -2 (< 0) reset start=1, tank=0 i = 1 (Fail) gas: 2 | cost: 4 Net: 2 - 4 = -2 tank: -2 (< 0) reset start=2, tank=0 i = 2 (Fail) gas: 3 | cost: 5 Net: 3 - 5 = -2 tank: -2 (< 0) reset start=3, tank=0 i = 3 (Success) gas: 4 | cost: 1 Net: 4 - 1 = +3 tank: 3 (>= 0) reaches next station! i = 4 (Next) gas: 5 | cost: 2 Net: 5 - 2 = +3 Accumulates... (Covered next) Live Variable Tracking & Accumulator State Active Tracking Variables • total (net surplus over whole trip): -3 • tank (fuel reserve since start): 3 • start (current candidate index): 3 Why Index 3 Succeeded - Stations 0, 1, 2 drained the tank below 0. - Proves no station from 0 up to 2 can be the valid starting point. - Index 3 successfully holds tank >= 0!
Tracing the Circular Gas Station Tour Step-by-Step diagram
Practice

Practice: Modify the Circuit and Test Your Understanding

Phase 4: Practice

Now that you have traced the original locked example gas=[1,2,3,4,5] and cost=[3,4,5,1,2], it is time to apply the running tank logic to a modified scenario. Imagine the fuel supply at each station is altered, but the cost requirements remain identical. Instead of starting with gas=[1,2,3,4,5], suppose we examine a new configuration where the stations provide gas=[2,3,4,1,5] while the costs remain cost=[3,4,5,1,2].
Before running the full pass in your head, consider what the total sum of gas versus the total sum of cost tells you about feasibility. Track how the running tank variable behaves as you cross each index from 0 to 4. Remember the core rule established in the model phase: whenever your tank drops below zero, every station from your current start up to is invalid as a starting point because any of them would fail before reaching .
Work through the sequence manually using a scratchpad or mental trace, updating total, tank, and start whenever a deficit occurs. Try to determine whether a valid starting index exists for this modified array, and if so, identify which station it is.
python
def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    # Modified test case
    # gas  = [2, 3, 4, 1, 5]
    # cost = [3, 4, 5, 1, 2]
    pass
Apply

Applying the Circular Tour Pattern to Battery and Route Problems

Phase 5: The Transfer

Now that you have mastered the circular gas station tour with our locked arrays gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2], let's step back and look at the broader architectural pattern. The single-pass accumulator trick we used—tracking both a local tank to reset our start point and a global total to verify feasibility—is not just for cars on a circular road. It is a general template for any bounded, cyclic resource problem where a deficit at index i invalidates every starting candidate from our current start up to i.
Imagine you are designing a power-management system for an autonomous drone patrolling a closed-loop grid of charging pads and sensor towers. Each pad i provides a certain kilowatt-hours of solar generation (gas[i]), but moving to the next pad consumes energy (cost[i]). Just like our gas and cost arrays, if the drone's battery dips below zero while traveling from station 3 to 4, no station from 0 to 3 could have possibly supplied enough surplus to survive that exact drop. The mathematical proof guarantees that we can safely jump our start pointer to i + 1 without ever re-evaluating the skipped indices.
This same reduction applies whenever you encounter a circular sequence requiring a prefix-sum invariant with resets. Whether you are balancing circular delivery fleets, allocating circumferential bandwidth tokens in distributed nodes, or scheduling jobs around a ring buffer, the core insight remains identical: local failures instantly eliminate whole ranges of starting states, turning an simulation into a single linear sweep.
python
def can_complete_circuit_generalized(generation: list[int], consumption: list[int]) -> int:
    if sum(generation) < sum(consumption):
        return -1
    
    current_balance = 0
    optimal_start = 0
    
    for i in range(len(generation)):
        current_balance += generation[i] - consumption[i]
        if current_balance < 0:
            optimal_start = i + 1
            current_balance = 0
            
    return optimal_start
By keeping the global sum check separate from the local running balance, you avoid redundant checks and leverage the exact same mechanics we traced through our five-station tour.
python
def can_complete_circuit_generalized(generation: list[int], consumption: list[int]) -> int:
    # Apply the single-pass circular tour pattern here
    pass

FAQ

Why does starting at station 3 work for gas=[1,2,3,4,5] and cost=[3,4,5,1,2]?
Starting at station 3 provides 4 units of gas with a cost of 1 to reach station 4, leaving a surplus. Continuing through station 4 and wrapping around to stations 0, 1, and 2 keeps the tank above zero at every step.
How can this problem be solved in O(n) time instead of O(n^2)?
By keeping track of the total surplus and current tank levels in a single pass, we can identify if a solution exists and immediately reset our starting candidate whenever the tank drops below zero.
What is the primary condition for a circular tour to exist?
A valid starting station exists if and only if the sum of all gas values is greater than or equal to the sum of all cost values.
What happens if multiple valid starting stations exist?
If a valid tour exists, the problem guarantees a unique solution, so you only ever need to find the single starting index that completes the loop.

Keep learning