Gas Station LeetCode: Greedy One-Pass Solution Explained

Gas station leetcode (#134) is one of those problems that looks like it requires brute force but hides a clean greedy solution. The premise is deceptively simple: you have a circular route of gas stations, each offering some fuel and costing some fuel to reach the next. Find the starting station that lets you complete the full loop, or return -1 if no such station exists.

What makes this problem special is the elegant proof at its core. If the total gas available across all stations is greater than or equal to the total cost, then a valid starting station is guaranteed to exist. And you can find that station in a single pass through the array. No nested loops, no simulation from every index.

This walkthrough covers the greedy insight behind LeetCode 134 solution, walks through the algorithm step by step, and shows you exactly why the reset strategy works. By the end, you will see why gas station greedy is a textbook example of the pattern.

You are given two arrays of the same length: gas[i] represents the fuel you pick up at station i, and cost[i] represents the fuel needed to travel from station i to station i+1. The route is circular, meaning after the last station you wrap back to station 0. Your tank starts empty.

The question is straightforward: is there a starting station index such that you can travel around the entire circuit once without your tank going negative at any point? If yes, return that index. If no, return -1. The problem guarantees that if a solution exists, it is unique.

A brute-force approach would try starting at every station and simulate the trip — O(n^2) time. But the circular route gas structure of this problem allows something far better. The greedy approach solves it in O(n) time and O(1) space.

The gas station one pass algorithm answers two questions simultaneously. First: CAN you complete the circuit at all? Second: WHERE should you start? Both answers emerge from tracking two running sums as you iterate through the stations.

The feasibility check is simple. Add up all the gas values and subtract all the cost values. If total_tank (total gas minus total cost) is negative, there is not enough fuel in the system for any starting point to work. Return -1 immediately.

The starting point discovery uses a reset strategy. Maintain a current_tank that tracks the fuel surplus as you drive from the current candidate start. When current_tank drops below zero at station i, it means the current candidate cannot reach station i+1. So you reset: set the new candidate start to i+1 and reset current_tank to zero.

The key insight is that if current_tank goes negative at station i starting from station s, then no station between s and i can be a valid start either. Each of those stations would arrive at station i with even less fuel than station s did. This is why a single pass is sufficient — you never need to revisit skipped candidates.

The gas station explained in code is remarkably concise. You need three variables: total_tank to track the global feasibility, current_tank to track the local surplus from your candidate start, and start to hold the candidate index. Initialize all three to zero.

Loop through every station from 0 to n-1. At each station i, compute the net gain: gas[i] - cost[i]. Add it to both total_tank and current_tank. If current_tank drops below zero, reset start to i+1 and current_tank to 0.

After the loop, check total_tank. If it is >= 0, return start. Otherwise, return -1. That is the entire algorithm — one loop, three variables, no extra arrays.

Let us trace through the classic example: gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. Total gas = 15, total cost = 15, so total_tank = 0. A solution must exist.

Starting with candidate start = 0. Station 0: net = 1-3 = -2, current_tank = -2. Tank went negative, so reset start = 1, current_tank = 0. Station 1: net = 2-4 = -2, current_tank = -2. Negative again, reset start = 2, current_tank = 0. Station 2: net = 3-5 = -2, current_tank = -2. Negative again, reset start = 3, current_tank = 0.

Station 3: net = 4-1 = 3, current_tank = 3. Positive — keep going. Station 4: net = 5-2 = 3, current_tank = 6. Still positive. Loop ends. total_tank = 0 >= 0, so return start = 3. Index 3 is the answer.

From station 3, the trip plays out: pick up 4, spend 1 to reach station 4 (tank = 3). Pick up 5, spend 2 to reach station 0 (tank = 6). Pick up 1, spend 3 to reach station 1 (tank = 4). Pick up 2, spend 4 to reach station 2 (tank = 2). Pick up 3, spend 5 to reach station 3 (tank = 0). Circuit complete.

The most important edge case is when total gas is strictly less than total cost. In that scenario, no starting index works regardless of the arrangement. The algorithm handles this naturally because total_tank will be negative, and you return -1.

A single-station case (n = 1) is trivially handled: if gas[0] >= cost[0], start at index 0. Otherwise return -1. The algorithm works without any special case because the loop runs once and the total_tank check covers it.

Watch for the case where the valid start is the last index. If all stations before n-1 collectively cause current_tank resets, the candidate may land on the final station. The greedy proof guarantees this is correct as long as total_tank >= 0.

Gas station greedy is a textbook example of the "running sum with reset" pattern. You maintain a cumulative value, and when it becomes invalid (negative), you restart from the next position. This same idea appears in maximum subarray (Kadane's algorithm), jump game, and other greedy circular tour problems.

The deeper lesson is the two-question pattern: "Can we do it?" and "Where do we start?" Many greedy problems split into a feasibility check and an optimization step. Recognizing this structure lets you avoid overthinking the proof — just track the global sum for feasibility and the local sum for the optimal choice.

If you want to internalize the gas station one pass pattern and similar greedy strategies, YeetCode flashcards break these problems into pattern-recognition drills. Instead of re-solving the same problem from scratch, you practice identifying the greedy signal — running surplus, reset trigger, feasibility check — until it becomes second nature.