LeetCode 134: Gas Station Solution in Python Explained

Problem Statement

In LeetCode 134, you’re given two integer arrays gas and cost of length n, where gas[i] is the gas available at station i, and cost[i] is the gas needed to travel from station i to i+1 (wrapping from n-1 to 0). Your task is to return the index of a starting station where a car with 0 initial gas can complete the circuit, collecting gas and using it to reach the next station, or -1 if impossible. This differs from path sum problems like LeetCode 113: Path Sum II, focusing on a circular array rather than a tree.

Constraints

• 1 <= gas.length == cost.length <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

Example

Let’s see some cases:

Copy codeInput: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation: Start at 3 (gas=4):
<ul>
<li>3->4: 4-1=3 gas left.</li>
<li>4->0: 3+5-2=6.</li>
<li>0->1: 6+1-3=4.</li>
<li>1->2: 4+2-4=2.</li>
<li>2->3: 2+3-5=0, completes circuit.</li>
</ul>

Copy codeInput: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation: No start allows completion:
<ul>
<li>0: 2-3=-1, fails.</li>
<li>1: 3-4=-1, fails.</li>
<li>2: 4-3=1, 1+2-4=-1, fails.</li>
</ul>

Copy codeInput: gas = [5,1,2,3,4], cost = [4,4,1,5,1]
Output: 4
Explanation: Start at 4 (gas=4):
<ul>
<li>4->0: 4-1=3.</li>
<li>0->1: 3+5-4=4.</li>
<li>1->2: 4+1-4=1.</li>
<li>2->3: 1+2-1=2.</li>
<li>3->4: 2+3-5=0, completes.</li>
</ul>

These examples show we’re finding a viable starting point.

Understanding the Problem

How do you solve LeetCode 134: Gas Station in Python? Take gas = [1,2,3,4,5], cost = [3,4,5,1,2]. We need a starting index where the car can complete the circuit—starting at 3 works, as gas collected covers costs (net gas ≥ 0 throughout). For [2,3,4], [3,4,3], total gas (9) equals total cost (9), but no start avoids negative gas, so -1. This isn’t a tree depth problem like LeetCode 111: Minimum Depth of Binary Tree; it’s about circular array traversal with resource constraints. We’ll use: 1. Greedy Single Pass: O(n) time, O(1) space—our best solution. 2. Brute Force Simulation: O(n²) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Greedy Single Pass Approach

Explanation

Greedy Single Pass checks if a circuit is possible by tracking total gas and total cost—if total gas < total cost, it’s impossible (-1). Otherwise, it finds the starting point by tracking the current tank level; if it drops below 0, reset it and move the start to the next station. This is the best solution due to its O(n) time complexity, O(1) space, and elegant use of a single pass to both validate feasibility and locate the start, leveraging the circular nature efficiently.

For gas = [1,2,3,4,5], cost = [3,4,5,1,2]:

• Total gas = 15, total cost = 15, possible.
• Tank: 1-3=-2 (reset, start=1), 2-4=-2 (reset, start=2), 3-5=-2 (reset, start=3), 4-1=3, 5-2=6, 1-3=4, 2-4=2, 3-5=0, completes from 3.

Step-by-Step Example

Example 1: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Goal: Return 3.

• Start: total_tank = 0, curr_tank = 0, start = 0.
• Step 1: i=0, curr_tank = 1-3 = -2.
• curr_tank < 0, reset curr_tank = 0, start = 1.
• total_tank = -2.
• Step 2: i=1, curr_tank = 2-4 = -2.
• Reset curr_tank = 0, start = 2.
• total_tank = -4.
• Step 3: i=2, curr_tank = 3-5 = -2.
• Reset curr_tank = 0, start = 3.
• total_tank = -6.
• Step 4: i=3, curr_tank = 4-1 = 3.
• total_tank = -3.
• Step 5: i=4, curr_tank = 3+5-2 = 6.
• total_tank = 1.
• Wraparound: Continue from 0.
• i=0, curr_tank = 6+1-3 = 4, total_tank = -1.
• i=1, curr_tank = 4+2-4 = 2, total_tank = -3.
• i=2, curr_tank = 2+3-5 = 0, total_tank = -5.
• Finish: total_tank = 0 (after full loop), return start = 3.

Example 2: gas = [2,3,4], cost = [3,4,3]

Goal: Return -1.

• Start: total_tank = 0, curr_tank = 0, start = 0.
• Step 1: i=0, curr_tank = 2-3 = -1.
• Reset curr_tank = 0, start = 1.
• total_tank = -1.
• Step 2: i=1, curr_tank = 3-4 = -1.
• Reset curr_tank = 0, start = 2.
• total_tank = -2.
• Step 3: i=2, curr_tank = 4-3 = 1.
• total_tank = -1.
• Finish: total_tank = -1 < 0, return -1.

Example 3: gas = [5,1,2,3,4], cost = [4,4,1,5,1]

Goal: Return 4.

• Start: total_tank = 0, curr_tank = 0, start = 0.
• Step 1: i=0, curr_tank = 5-4 = 1, total_tank = 1.
• Step 2: i=1, curr_tank = 1+1-4 = -2.
• Reset curr_tank = 0, start = 2.
• total_tank = -1.
• Step 3: i=2, curr_tank = 2-1 = 1, total_tank = 0.
• Step 4: i=3, curr_tank = 1+3-5 = -1.
• Reset curr_tank = 0, start = 4.
• total_tank = -1.
• Step 5: i=4, curr_tank = 4-1 = 3, total_tank = 2.
• Wraparound: i=0, curr_tank = 3+5-4 = 4, total_tank = 3.
• Continue: i=1, curr_tank = 4+1-4 = 1, i=2, curr_tank = 2, i=3, curr_tank = 0, total_tank = 0.
• Finish: total_tank = 0, return start = 4.

How the Code Works (Greedy Single Pass) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    # Line 1: Initialize total and current tank levels
    total_tank = 0
    # Tracks net gas across all stations (e.g., initially 0)
    curr_tank = 0
    # Tracks gas for current segment (e.g., initially 0)

    # Line 2: Initialize starting station
    start = 0
    # Starting index candidate (e.g., initially 0)

    # Line 3: Iterate through all stations
    for i in range(len(gas)):
        # i = current station index (e.g., 0 to 4)

        # Line 4: Update total tank
        total_tank += gas[i] - cost[i]
        # Adds net gas (e.g., 1-3=-2, total_tank=-2)
        # Checks overall feasibility

        # Line 5: Update current tank
        curr_tank += gas[i] - cost[i]
        # Adds net gas to current segment (e.g., 1-3=-2)

        # Line 6: Check if current tank is negative
        if curr_tank < 0:
            # If tank drops below 0 (e.g., -2), can’t start here
            curr_tank = 0  # Reset for new segment (e.g., 0)
            start = i + 1  # Move start to next station (e.g., 1)

    # Line 7: Check if total gas suffices
    return start if total_tank >= 0 else -1
    # If total_tank ≥ 0 (e.g., 0), circuit possible, return start (e.g., 3)
    # Else (e.g., -1), impossible, return -1

This detailed breakdown clarifies how the greedy single-pass approach efficiently finds the starting station.

Alternative: Brute Force Simulation Approach

Explanation

Brute Force Simulation tries each station as a starting point, simulating the circuit by tracking gas levels and checking if the car can complete it without running out. It’s a straightforward alternative but less efficient, with O(n²) time due to repeated traversals, though it’s intuitive for understanding the problem.

For [1,2,3,4,5], [3,4,5,1,2]:

• Start 0: Fails at 0 (1-3=-2).
• Start 3: Completes (4-1=3, 5-2=6, etc.).
• Return 3.

Step-by-Step Example (Alternative)

For [1,2,3,4,5], [3,4,5,1,2]:

• Start 0: Tank = 1-3=-2, fails.
• Start 1: Tank = 2-4=-2, fails.
• Start 2: Tank = 3-5=-2, fails.
• Start 3: Tank = 4-1=3, 5-2=6, 1-3=4, 2-4=2, 3-5=0, completes.
• Finish: Return 3.

How the Code Works (Brute Force)

Copy codedef canCompleteCircuitBrute(gas: list[int], cost: list[int]) -> int:
    n = len(gas)
    for start in range(n):
        tank = 0
        for i in range(n):
            idx = (start + i) % n
            tank += gas[idx] - cost[idx]
            if tank < 0:
                break
        else:
            return start
    return -1

Complexity

• Greedy Single Pass:
• Time: O(n) – single pass.
• Space: O(1) – constant space.
• Brute Force Simulation:
• Time: O(n²) – n starts, up to n steps each.
• Space: O(1) – constant space.

Efficiency Notes

Greedy Single Pass is the best solution with O(n) time and O(1) space, offering efficiency and elegance—Brute Force Simulation uses O(n²) time, making it a clear but less efficient alternative, useful for smaller inputs or conceptual understanding.

Key Insights

• Greedy: Reset on failure, check total.
• Circular: Wraparound logic.
• Tank: Tracks gas feasibility.

Additional Example

For gas = [4,5,2,6,5], cost = [5,2,4,5,6]:

• Goal: 1.
• Greedy: Start=1, completes circuit.

Edge Cases

• Single Station: gas=[1], cost=[1] → 0.
• All Fail: gas=[1], cost=[2] → -1.
• Equal: gas=[2,2], cost=[2,2] → 0.

Both solutions handle these well.

Final Thoughts

LeetCode 134: Gas Station in Python is a clever circular challenge. The Greedy Single Pass solution excels with its efficiency and clarity, while Brute Force Simulation offers an intuitive approach. Want more? Try LeetCode 112: Path Sum for tree path sums or LeetCode 108: Convert Sorted Array to Binary Search Tree for BST basics. Ready to practice? Solve LeetCode 134 on LeetCode with gas=[1,2,3,4,5], cost=[3,4,5,1,2], aiming for 3—test your skills now!