Gas Station LeetCode 134 Deep Dive

LeetCode 134 Gas Station presents a circular route with n stations. At each station i you can collect gas[i] units of fuel, and it costs cost[i] units of fuel to travel from station i to station i+1. The final station connects back to station 0, completing the loop.

Your task: find the index of the starting station from which you can complete the full circular route without your fuel tank ever going negative. If no such starting point exists, return -1. The problem guarantees at most one valid answer.

This is a classic greedy problem that trips up candidates who reach for simulation or brute force. The elegant O(n) solution emerges once you see how local deficits and global surplus interact.

The key observation is that if the total gas across all stations is at least equal to the total cost, a solution is guaranteed to exist — and it will be unique. This means you can solve existence and identification in the same pass.

Track a running tank as you iterate through every station. When the tank drops below zero at station j, you know that neither the current candidate start nor any station between the original start and j can reach j. Reset the candidate start to j+1 and reset the tank to zero.

After completing the loop, if totalGas >= totalCost, the last candidate start you settled on is the answer. Otherwise return -1. The entire algorithm runs in O(n) time with O(1) extra space.

The algorithm uses four variables: totalGas, totalCost, tank, and start. All are initialised to zero. A single for loop processes every station, updating all four values.

After the loop, a single conditional determines the answer: if totalGas >= totalCost the circuit is completable and start is the answer; otherwise return -1. No second pass, no nested loops, no auxiliary data structures.

Because the problem guarantees at most one valid start, the greedy candidate accumulated during the sweep is provably correct whenever a solution exists.

Every station before the most recent reset point caused the tank to go negative when reached from some earlier candidate. That means they are all provably invalid as starting points. The reset point j+1 is the earliest station where the cumulative net gain from j+1 onward stays non-negative throughout the remaining route.

Formally, the greedy start is the station where the suffix sum of (gas[i] - cost[i]) is maximized. If the total surplus is non-negative, this suffix must be large enough to absorb the entire deficit accumulated in the prefix before it.

This is not just a heuristic — it is a guarantee. The uniqueness property of the problem means there is exactly one station with this property whenever a solution exists, and the greedy pass finds it without ever backtracking.

Take gas = [1,2,3,4,5] and cost = [3,4,5,1,2]. Total gas = 15, total cost = 15. They are equal, so a solution is guaranteed. Now trace the greedy sweep.

At station 0: tank = 1-3 = -2 (negative). Reset start=1, tank=0. At station 1: tank = 2-4 = -2 (negative). Reset start=2, tank=0. At station 2: tank = 3-5 = -2 (negative). Reset start=3, tank=0.

From station 3 onward the tank stays non-negative: station 3 gives 4-1=3; station 4 gives 3+(5-2)=6; wrapping to station 0 gives 6+(1-3)=4; station 1 gives 4+(2-4)=2; station 2 gives 2+(3-5)=0. Tank never went negative. Answer: start = 3.

In Python the solution is a single for loop: iterate i from 0 to n-1, update tank += gas[i] - cost[i], update totalGas and totalCost, and if tank < 0 reset start = i+1 and tank = 0. Return start if totalGas >= totalCost else -1. Time complexity O(n), space O(1).

In Java the structure is identical: a for loop with the same four assignments and a single conditional reset. The return statement mirrors the Python version. Both implementations are around 10 lines of code with no imports beyond basic I/O.

The elegance of this solution is that it collapses what might feel like a two-pass problem into one. The global feasibility check (totalGas vs totalCost) and the local candidate identification (tracking tank resets) happen simultaneously in the same loop.

Gas Station belongs to the circular greedy family. Can Place Flowers (LeetCode 605) uses a similar local-decision pattern: decide at each position whether to plant without looking ahead, trusting that greedy local choices produce a globally correct count.

Dota2 Senate (LeetCode 649) applies greedy elimination in a circular sequence — each senator greedily bans the nearest opposing senator, a pattern that mirrors the station-skipping logic here. Non-Overlapping Intervals (LeetCode 435) uses greedy sorting to minimize removals, the same principle of eliminating provably suboptimal candidates early.

All of these problems share the core greedy insight: when you can prove that a local choice eliminates a class of worse alternatives, you can make that choice confidently and move on. Mastering Gas Station builds the intuition for the entire greedy algorithm family.