Common Greedy Patterns - Learning Module

Loading content...

0/276

Gas Station Problem

The Road Trip Puzzle

Picture this: You're planning a road trip around a circular route with multiple gas stations. Your car starts with an empty tank. Each station offers a certain amount of gas, and traveling to the next station consumes a certain amount. The question is profound: Can you complete the circuit? And if so, where should you start?

This seemingly simple puzzle—the Gas Station Problem—is a masterpiece of algorithmic design. It appears in interviews at top tech companies, captures essential reasoning about resource management, and admits a beautiful O(n) greedy solution that feels almost magical once understood.

What You Will Learn

By the end of this page, you will master the gas station problem completely: the formal problem definition, the brute force approach, the elegant greedy solution, the mathematical proof of why it works, implementation details, variations, and the deep insight that makes this problem a favorite in algorithm courses.

Problem Formalization

The Gas Station Problem (Circular Route):

Input:

n gas stations arranged in a circle, numbered 0 to n-1
Array gas[i] = amount of gas available at station i
Array cost[i] = gas needed to travel from station i to station (i+1) mod n
Car has an unlimited tank capacity
Car starts with an empty tank

Output:

The starting station index s such that starting at s with empty tank, filling up at each station, the car can complete one full circuit
Return -1 if no valid starting point exists

Constraints:

The car must never run out of gas mid-journey
At each station, the car first collects gas, then travels to the next station
The circuit is complete when returning to the starting station

Visual Example:

        Station 0
          ⛽ gas=1
          → cost=3
            ↘
Station 3     ➡      Station 1
⛽ gas=4              ⛽ gas=2  
→ cost=1              → cost=4
    ↖              ↙
        Station 2
          ⛽ gas=3
          → cost=2

gas = [1, 2, 3, 4] cost = [3, 4, 2, 1]

Analysis:

Net gain at each station: net[i] = gas[i] - cost[i]
Station 0: 1 - 3 = -2 (deficit)
Station 1: 2 - 4 = -2 (deficit)
Station 2: 3 - 2 = +1 (surplus)
Station 3: 4 - 1 = +3 (surplus)

Total net: -2 + (-2) + 1 + 3 = 0

Since total net ≥ 0, a solution exists. But where to start?

The Fundamental Insight

If the total gas available ≥ total cost, a solution always exists. The key insight is that there's at most one valid starting point (sometimes zero if total is negative). We don't need to try all starting points—we can find the answer in one pass.

The Brute Force Approach

Before optimizing, let's understand the straightforward approach:

GAS-STATION-BRUTE-FORCE(gas[], cost[]):
    n = length(gas)
    
    FOR start = 0 TO n-1:
        tank = 0
        can_complete = true
        
        FOR i = 0 TO n-1:
            station = (start + i) mod n
            tank += gas[station]
            tank -= cost[station]
            
            IF tank < 0:
                can_complete = false
                BREAK
        
        IF can_complete:
            RETURN start
    
    RETURN -1  // No valid starting point

gas_station_brute.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from typing import List
 
def gas_station_brute_force(gas: List[int], cost: List[int]) -> int:
    """
    Brute force O(n²) solution: try each starting point.
    """
    n = len(gas)
    
    for start in range(n):
        tank = 0
        can_complete = True
        
        for i in range(n):
            station = (start + i) % n
            tank += gas[station]  # Fill up
            tank -= cost[station]  # Travel to next
            
            if tank < 0:
                can_complete = False
                break
        
        if can_complete:
            return start
    
    return -1
 
 
def simulate_journey(gas: List[int], cost: List[int], start: int) -> None:
    """Simulate and visualize the journey from a starting point."""
    n = len(gas)
    tank = 0
    
    print(f"\nStarting from station {start}:")
    print("-" * 50)
    
    for i in range(n):
        station = (start + i) % n
        next_station = (station + 1) % n
        
        print(f"Station {station}: tank={tank} + gas={gas[station]} = {tank + gas[station]}")
        tank += gas[station]
        
        print(f"  Travel to station {next_station}: {tank} - cost={cost[station]} = {tank - cost[station]}")
        tank -= cost[station]
        
        if tank < 0:
            print(f"  ❌ RAN OUT OF GAS!")
            return
    
    print(f"\n✅ Completed circuit! Final tank: {tank}")
 
 
# Example
gas = [1, 2, 3, 4]
cost = [3, 4, 2, 1]
 
result = gas_station_brute_force(gas, cost)
print(f"Valid starting station: {result}")
simulate_journey(gas, cost, result)

Complexity Analysis:

Time: O(n²) — For each of n starting points, we simulate n steps
Space: O(1) — Only constant extra space

Why This is Inefficient:

If we fail at station j starting from station i, we've learned that stations i through j-1 are all bad starting points. Starting from any of them would still fail at j. The brute force approach ignores this information and tries each station independently.

The greedy insight is to accumulate this knowledge and skip impossible starting points.

The Greedy Solution: One Pass

The O(n) greedy solution is elegant. It exploits two key observations:

Observation 1: Total Sum Condition

If Σgas[i] < Σcost[i], no starting point works—there isn't enough gas in the system.

If Σgas[i] ≥ Σcost[i], exactly one starting point works (could be any if sum equals exactly).

Observation 2: Failure Point Skipping

If we start at station s and first fail at station j (tank goes negative), then no station between s and j (inclusive of s) can be a valid start.

Why? Any station k between s and j would reach j with even less gas (since starting at s gave us some buffer from s to k).

The Greedy Principle

When we fail at station j, restart from j+1 with an empty tank. All stations before j+1 are proven invalid. If we complete a circuit from some station s, we're guaranteed that s is the unique answer (if total sum ≥ 0).

The Algorithm:

GAS-STATION-GREEDY(gas[], cost[]):
    total_tank = 0      // Total gas - cost for entire circuit
    current_tank = 0    // Current tank from candidate start
    start_station = 0   // Candidate answer
    
    FOR i = 0 TO n-1:
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]
        
        IF current_tank < 0:
            // Can't reach station i+1 from current start
            // Reset: try starting from i+1
            start_station = i + 1
            current_tank = 0
    
    IF total_tank >= 0:
        RETURN start_station
    ELSE:
        RETURN -1  // Not enough gas overall

gas_station_greedy.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
def can_complete_circuit(gas: List[int], cost: List[int]) -> int:
    """
    O(n) greedy solution for gas station problem.
    
    Args:
        gas: Amount of gas at each station
        cost: Cost to travel to next station
        
    Returns:
        Starting station index, or -1 if impossible
    """
    n = len(gas)
    
    total_tank = 0     # Tracks overall feasibility
    current_tank = 0   # Tracks current segment feasibility
    start_station = 0  # Candidate starting station
    
    for i in range(n):
        net_gain = gas[i] - cost[i]
        total_tank += net_gain
        current_tank += net_gain
        
        if current_tank < 0:
            # Cannot proceed from current start
            # Try starting fresh from the next station
            start_station = i + 1
            current_tank = 0
    
    # If overall we have enough gas, start_station is valid
    return start_station if total_tank >= 0 else -1
 
 
def can_complete_circuit_verbose(gas: List[int], cost: List[int]) -> int:
    """Same algorithm with detailed tracing."""
    n = len(gas)
    total_tank = 0
    current_tank = 0
    start_station = 0
    
    print("\nGreedy algorithm trace:")
    print("=" * 60)
    print(f"{'i':>3} | {'gas':>4} | {'cost':>4} | {'net':>4} | {'current':>8} | {'start':>6} | Action")
    print("-" * 60)
    
    for i in range(n):
        net = gas[i] - cost[i]
        total_tank += net
        current_tank += net
        
        action = ""
        if current_tank < 0:
            action = f"Reset! start -> {i + 1}"
            start_station = i + 1
            current_tank = 0
        
        print(f"{i:>3} | {gas[i]:>4} | {cost[i]:>4} | {net:>+4} | {current_tank:>8} | {start_station:>6} | {action}")
    
    print("-" * 60)
    print(f"Total tank: {total_tank}")
    
    if total_tank >= 0:
        print(f"✅ Solution: start at station {start_station}")
        return start_station
    else:
        print("❌ No solution exists")
        return -1
 
 
# Example
gas = [1, 2, 3, 4]
cost = [3, 4, 2, 1]
result = can_complete_circuit_verbose(gas, cost)

Trace Through the Example:

gas = [1, 2, 3, 4], cost = [3, 4, 2, 1]

i	gas	cost	net	current_tank	start	Action
0	1	3	-2	-2	0 → 1	Reset!
1	2	4	-2	-2	1 → 2	Reset!
2	3	2	+1	+1	2	-
3	4	1	+3	+4	2	-

total_tank = -2 + (-2) + 1 + 3 = 0 ≥ 0 ✓

Answer: Start at station 2

Verification: Starting at station 2:

Station 2: +3 gas, -2 cost → tank = 1
Station 3: +4 gas, -1 cost → tank = 4
Station 0: +1 gas, -3 cost → tank = 2
Station 1: +2 gas, -4 cost → tank = 0

Complete! ✓

Correctness Proof

The greedy algorithm's correctness relies on two key lemmas:

Lemma 1: Feasibility Condition

A valid starting point exists if and only if Σgas[i] ≥ Σcost[i].

Proof: If total gas < total cost, we'll eventually run out regardless of where we start. If total gas ≥ total cost, we can always find a valid starting point (proven by Lemma 2).

Lemma 2: Skip Invalid Starts

If starting from station s, we first fail at station j (i.e., current_tank goes negative just after leaving station j), then no station k where s ≤ k ≤ j can be a valid starting point.

Proof: Consider any station k between s and j. When we started from s, we reached k with tank ≥ 0. From k to j, our tank went negative. If we started directly from k with tank = 0, we'd have even less fuel at each intermediate point, so we'd still fail at or before j.

Main Theorem:

The greedy algorithm returns the correct starting station (or -1 if none exists).

Proof:

Case 1: total_tank < 0 The algorithm returns -1, which is correct by Lemma 1.

Case 2: total_tank ≥ 0 Let s be the starting station returned by the algorithm. By construction, starting from s and traversing stations s, s+1, ..., n-1, the current_tank never goes negative.

We need to show s can also traverse 0, 1, ..., s-1.

Let:

A = sum of (gas[i] - cost[i]) for i = s to n-1 (portion we've verified)
B = sum of (gas[i] - cost[i]) for i = 0 to s-1 (remaining portion)

We know:

A ≥ 0 (current_tank never went negative)
A + B = total_tank ≥ 0

After completing s to n-1, our tank has exactly A fuel. We need to complete 0 to s-1, which requires 0 or more fuel at each step.

Since B = total_tank - A and we have A fuel, and the net requirement for section 0 to s-1 is -B (we need B units to complete it), our tank after 0 to s-1 is A + B = total_tank ≥ 0.

The key insight: each failed segment before s had negative sum. Segment s to n-1 has sum A ≥ 0. Segment 0 to s-1 has sum B = total_tank - A. Since we're starting with A fuel and total_tank ≥ 0, we're guaranteed to complete.

∎

Intuition Behind the Proof

Think of it as partitioning the circle into two arcs: s → end (verified during algorithm) and start → s-1 (to verify). The algorithm ensures the first arc is completable. The total sum condition ensures the second arc's deficit (if any) is covered by the surplus from the first arc.

Complexity Analysis

Algorithm Complexity Comparison
Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	Try each starting point
Greedy (One Pass)	O(n)	O(1)	Skip invalid starts intelligently

Why O(n) is Optimal:

We must examine each station at least once to know the gas and cost values. Therefore, Ω(n) is a lower bound. Our greedy solution achieves this—each station is visited exactly once.

Space Efficiency:

The algorithm uses only three integer variables regardless of input size:

total_tank: Running total for feasibility check
current_tank: Running total for current segment
start_station: Candidate answer

This O(1) space is a significant advantage for memory-constrained environments.

Optimal in Every Dimension

The greedy gas station algorithm is simultaneously optimal in time (O(n)) and space (O(1)). It's a rare algorithm that achieves best-possible bounds on both dimensions—no preprocessing, no extra data structures, just clean iteration.

Edge Cases and Variations

Critical Edge Cases:

Edge Cases to Consider

•Single Station: n=1, gas=[5], cost=[3] → Answer: 0 (can complete trivially)
•All Zeros: gas=[0,0,0], cost=[0,0,0] → Answer: 0 (any start works)
•Exactly Balanced: Each gas[i] = cost[i] → Answer: 0 (any start works, tank stays 0)
•Last Station Valid: Only station n-1 is valid → Algorithm correctly identifies it
•Start at 0 Optimal: Sometimes station 0 is the answer despite resets during simulation

gas_station_edge_cases.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def test_edge_cases():
    """Test edge cases for the gas station algorithm."""
    
    test_cases = [
        # (gas, cost, expected, description)
        ([5], [3], 0, "Single station with surplus"),
        ([3], [5], -1, "Single station with deficit"),
        ([0, 0, 0], [0, 0, 0], 0, "All zeros"),
        ([1, 1, 1], [1, 1, 1], 0, "Exactly balanced"),
        ([3, 1, 1], [1, 2, 2], 0, "Start at 0 is optimal"),
        ([2, 3, 4], [3, 4, 3], -1, "No solution exists"),
        ([5, 1, 2, 3, 4], [4, 4, 1, 5, 1], 4, "Last station is answer"),
    ]
    
    print("Edge Case Testing:")
    print("=" * 70)
    
    for gas, cost, expected, desc in test_cases:
        result = can_complete_circuit(gas, cost)
        status = "✓" if result == expected else "✗"
        print(f"{status} {desc}")
        print(f"   gas={gas}, cost={cost}")
        print(f"   Expected: {expected}, Got: {result}")
        print()
 
test_edge_cases()

Problem Variations:

Variation	Modification	Approach
Minimum fuel to start	Gas at stations, but can start with fuel	Binary search on starting fuel
Multiple valid starts	List all valid starting stations	If total ≥ 0, all equivalent (total = 0 case) or exactly one
Bidirectional travel	Can go clockwise or counterclockwise	Run algorithm both ways
Limited tank capacity	Tank can hold at most C fuel	More complex; may need DP
Variable speed	Fuel consumption varies with speed	Different cost model

Real-World Applications

The gas station problem models various circular resource-consumption scenarios:

Practical Applications

•Circular Bus Routes: Can a bus complete its route given fuel stations and consumption? Where should it start its shift?
•Battery-Powered Drones: Delivery drones with charging stations along a route—find viable patrol starting points.
•Resource Pipeline Management: Circular water or gas pipelines with input/output nodes—ensure positive pressure throughout.
•Circular Assembly Lines: Production lines where each station adds and consumes resources—find valid initialization points.
•Power Grid Loops: Ring networks where generators and consumers must balance—where to start energization.
•Cash Flow Analysis: Circular payment schedules where income and expenses occur at different points.

Generalization: Circular Prefix Problems

The gas station problem belongs to a broader class: circular prefix sum problems. Given a circular array of values, find a starting point such that all prefix sums (from that point, wrapping around) are non-negative.

This abstraction appears in:

Balancing parentheses starting from different positions
Circular buffer management
Round-robin scheduling with resource constraints
Game theory (can a player complete a circular game board?)

Interview Perspective

The gas station problem is a LeetCode classic (Problem #134) and frequently appears in interviews. Here's how to approach it:

Problem-Solving Steps

•Understand the circular nature
•Note: unlimited tank capacity
•Identify feasibility condition (total sum)
•Explain the greedy skip principle
•Handle edge case: start_station = n

Common Mistakes

•Forgetting to reset current_tank
•Not handling start_station = n (returns -1 via total check)
•Trying O(n²) when O(n) is expected
•Confusing the two tank variables
•Missing the modular wraparound in verification

Interview Script

"This is the classic gas station problem. Key insight: if total gas ≥ total cost, a solution exists. The greedy approach works by tracking current tank—when it goes negative, we reset and try the next station as our new candidate. This works because if you can't reach station j from station i, you definitely can't reach it from any station between them. One pass, O(n) time, O(1) space."

Summary: The Gas Station Pattern

Key Takeaways

•Problem: Find a starting station on a circular route to complete one circuit without running out of gas.
•Feasibility: Solution exists iff total gas ≥ total cost.
•Greedy Strategy: Track current tank; when negative, reset start to next station.
•Why It Works: If we fail at station j from station s, all stations s to j are invalid starts.
•Complexity: O(n) time, O(1) space—optimal in both dimensions.
•Pattern Recognition: Circular prefix sum with non-negativity constraint.

The Deeper Lesson:

The gas station problem exemplifies information accumulation in greedy algorithms. Instead of treating each starting point independently (O(n²)), we learn from failures and skip impossible options. This "failure provides information" insight recurs across algorithms:

KMP pattern matching: failure links skip redundant comparisons
Two-pointer techniques: one pointer's advancement informs the other
Monotonic stacks: elements popped are proven irrelevant

Recognizing when failures eliminate multiple candidates—not just one—is the key to transforming brute force into elegance.

Page Complete

You've mastered the gas station problem—its elegant greedy solution, mathematical proof, and broader applicability to circular resource problems. Next, we'll explore jump game variations, completing our tour of essential greedy patterns.