LeetCode · #134

Gas Station Solution

There are n gas stations along a circular route. Determine if you can complete the circuit and return the starting station index.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #134

🏗️

Pattern

Greedy — surplus tracking

Given arrays gas[i] (fuel gained at station i) and cost[i] (fuel to travel to station i+1), find the starting station to complete a full circular trip. Return -1 if impossible. If a solution exists, it is unique.

Example

Input: gas  = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3 // Start at station 3: tank=4-1=3→3+5-2=6→6+1-3=4→4+2-4=2→2+3-5=0. ✓

Constraints

• n == gas.length == cost.length • 1 ≤ n ≤ 10⁵ • 0 ≤ gas[i], cost[i] ≤ 10⁴

Section Two · Approach 1

Brute Force — O(n²)

Try each station as starting point. Simulate full circle, track tank. If tank goes negative → this start fails.

Problem: O(n²). The greedy insight: if starting at s and failing at f, no station between s and f is valid (they all have less fuel at f). Jump start to f+1. Combined with total fuel check.

Java — O(n²)

 class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int s = 0; s < n; s++) {
int tank = 0; boolean ok = true;
for (int j = 0; j < n; j++) {
int idx = (s + j) % n;
                tank += gas[idx] - cost[idx];
if (tank < 0) { ok = false; break; }
            }
if (ok) return s;
        }
return -1;
    }
}

Python — O(n²)

 class Solution:
def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        n = len(gas)
for s in range(n):
            tank = 0 if all((tank := tank + gas[(s+j)%n] - cost[(s+j)%n]) >= 0 for j in range(n)):
return s
return -1

Section Three · Approach 2

Greedy — O(n) time, O(1) space

Two insights: (1) If totalGas < totalCost, impossible. (2) Track running tank. When it goes negative, reset start to next station and reset tank. The final start is the answer.

💡 Mental model: Imagine driving a ring road. At each station you fill up and burn fuel to the next. If your total fuel across all stations ≥ total cost, a solution exists. The "where to start" question: drive from station 0. When your tank runs dry at station f, you know stations 0 through f are all bad starts (they all hit the same deficit). Start fresh from f+1. By the end, the last candidate standing is guaranteed correct.

Algorithm

totalSurplus = 0, tank = 0, start = 0.
For each station i: surplus = gas[i] - cost[i]. totalSurplus += surplus. tank += surplus.
If tank < 0: start = i + 1, tank = 0.
Return totalSurplus >= 0 ? start : -1.

🎯 When to recognize this pattern: "Circular route with gains and costs at each stop." The signal: circular array + net surplus + find starting point. The key greedy property: if you can't reach station f from station s, no station between s and f works either — they arrive at f with even less fuel.

Section Four · Trace

Visual Walkthrough

Trace for gas=[1,2,3,4,5], cost=[3,4,5,1,2].

Gas Station — Greedy

Section Five · Implementation

Code — Java & Python

Java — Greedy

 class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int surplus = gas[i] - cost[i];
            total += surplus;
            tank  += surplus;
if (tank < 0) { // can't reach next from current start
start = i + 1;
                tank = 0;
            }
        }
return total >= 0 ? start : -1;
    }
}

Python — Greedy

 class Solution:
def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total = tank = start = 0 for i in range(len(gas)):
            surplus = gas[i] - cost[i]
            total += surplus
            tank += surplus
if tank < 0:
                start = i + 1
tank = 0 return start if total >= 0 else -1

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force	O(n²)	O(1)	Try each start
Greedy ← optimal	O(n)	O(1)	Single pass; skip impossible starts

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Impossible	`gas=[1,1], cost=[2,2]`	totalSurplus = -2 < 0. Return -1.
Single station	`gas=[5], cost=[3]`	Start and end at 0. Return 0.
Start at last	`gas=[5,1,1], cost=[1,3,4]`	Start at index 0: surplus=[4,-2,-3]. start=0 works.
All equal	`gas=[3,3,3], cost=[3,3,3]`	Every station works. start=0.

⚠ Common Mistake: Forgetting the total >= 0 check. Without it, start might point to a valid-looking index even when the total fuel is insufficient. The running tank tracks "can we go from start to end," but the total check ensures "can we go all the way around." Both are needed.

← Back to Greedy problems

LearningTree

LC 134 · Gas Station — Solution & Explanation | DSA Guide