LeetCode 134 - Gas Station

The problem describes a circular route containing n gas stations. At each station i, you can collect gas[i] units of fuel. Traveling from station i to station (i + 1) % n consumes cost[i] units of fuel.

leetcodemediumarraygreedy

LeetCode Problem 134

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem describes a circular route containing n gas stations. At each station i, you can collect gas[i] units of fuel. Traveling from station i to station (i + 1) % n consumes cost[i] units of fuel.

You must determine whether there exists a starting station such that a car beginning with an empty tank can complete one full loop around the circle without ever running out of gas. If such a station exists, the problem guarantees that the answer is unique.

The input consists of two arrays:

  • gas[i] represents how much fuel you gain at station i
  • cost[i] represents how much fuel is needed to travel from station i to the next station

The expected output is:

  • The index of the valid starting station if completing the circuit is possible
  • -1 if no valid starting station exists

The constraints are important:

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

Since n can be as large as 100,000, any solution worse than linear or near-linear time is likely too slow. This immediately rules out expensive nested simulations for every station.

Several edge cases are important:

  • The total gas across all stations may be less than the total cost, making completion impossible
  • Some stations may individually fail immediately, even if the overall route is possible
  • Arrays of length 1 must still work correctly
  • Gas and cost values can both be zero
  • The valid start may appear late in the array after many failed attempts

The problem also guarantees uniqueness of the answer when a solution exists, which simplifies reasoning about the optimal solution.

Approaches

Brute Force Approach

The most direct solution is to try every station as a starting point.

For each starting index:

  1. Begin with an empty tank
  2. Simulate traveling around the entire circuit
  3. At every station:
  • Add available gas
  • Subtract travel cost
  1. If the tank ever becomes negative, this starting station fails
  2. If we successfully return to the start, return that index

This approach is correct because it explicitly checks every possible starting position. However, it is inefficient because each simulation may traverse nearly the entire array.

In the worst case:

  • There are n starting stations
  • Each simulation costs O(n)

This leads to O(n^2) time complexity, which is too slow for n = 10^5.

Optimal Greedy Approach

The key insight comes from understanding failure behavior.

Suppose we start at station A and fail at station B. This means that somewhere between A and B, the cumulative gas became insufficient.

Now consider any station between A and B as a potential starting point. None of them can succeed either.

Why?

Because starting later would only give us less gas before reaching the failure point. If the earlier start could not accumulate enough fuel, a later start cannot do better.

This observation allows us to skip many stations at once.

Another critical observation is:

  • If total gas across all stations is less than total cost, completing the circuit is impossible regardless of starting point

So the algorithm becomes:

  1. Check whether total gas is at least total cost
  2. Traverse the array once
  3. Maintain current fuel balance
  4. Whenever balance becomes negative:
  • Reset balance to zero
  • Set next station as the new candidate start

This works because any station before the failure point has already been proven invalid.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Simulates the full trip from every station
Optimal O(n) O(1) Uses greedy skipping based on failure intervals

Algorithm Walkthrough

Optimal Greedy Algorithm

  1. Initialize two variables:
  • total_balance, tracks total gas minus total cost across the entire route
  • current_balance, tracks gas remaining while testing the current candidate start
  1. Initialize start_index = 0.
  2. Traverse every station from left to right.
  3. At each station:
  • Compute difference = gas[i] - cost[i]
  • Add this value to both total_balance and current_balance
  1. If current_balance becomes negative:
  • The current starting station cannot work
  • Any station between the current start and this failure point also cannot work
  • Set start_index = i + 1
  • Reset current_balance = 0
  1. Continue scanning the remaining stations.
  2. After processing all stations:
  • If total_balance < 0, return -1
  • Otherwise, return start_index

Why it works

The algorithm relies on a greedy invariant:

If starting from station A causes failure at station B, then no station between A and B can be a valid starting point.

This is because all intermediate stations would begin with less accumulated fuel than starting at A.

Therefore, once failure occurs, we can safely skip every station in that interval and move directly to B + 1.

The final candidate works because the total gas is sufficient to cover the total cost globally.

Python Solution

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total_balance = 0
        current_balance = 0
        start_index = 0

        for i in range(len(gas)):
            difference = gas[i] - cost[i]

            total_balance += difference
            current_balance += difference

            if current_balance < 0:
                start_index = i + 1
                current_balance = 0

        if total_balance < 0:
            return -1

        return start_index

The implementation closely follows the greedy algorithm.

total_balance determines whether the journey is globally possible. If the total gas available is smaller than the total travel cost, no solution exists.

current_balance represents the remaining fuel while evaluating the current candidate starting station. As we iterate through the stations, we continuously update this value.

Whenever current_balance becomes negative, we know the current starting point cannot succeed. More importantly, all stations between the current start and the failure point are also invalid. Therefore, we move the candidate start to the next station and reset the running balance.

At the end of the traversal, if the overall balance is non-negative, the stored start_index is guaranteed to be the unique valid answer.

Go Solution

func canCompleteCircuit(gas []int, cost []int) int {
    totalBalance := 0
    currentBalance := 0
    startIndex := 0

    for i := 0; i < len(gas); i++ {
        difference := gas[i] - cost[i]

        totalBalance += difference
        currentBalance += difference

        if currentBalance < 0 {
            startIndex = i + 1
            currentBalance = 0
        }
    }

    if totalBalance < 0 {
        return -1
    }

    return startIndex
}

The Go implementation mirrors the Python logic almost exactly.

Go uses explicit variable declarations and integer arithmetic with int. Since the constraints are relatively small, integer overflow is not a concern here.

Slices are used directly, and no extra memory allocation is required. The algorithm remains fully iterative and constant-space.

Worked Examples

Example 1

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

We compute the difference at each station:

Index Gas Cost Difference Current Balance Total Balance Start Index
0 1 3 -2 -2 -2 0
Reset 0 -2 1
1 2 4 -2 -2 -4 1
Reset 0 -4 2
2 3 5 -2 -2 -6 2
Reset 0 -6 3
3 4 1 3 3 -3 3
4 5 2 3 6 0 3

Final values:

  • total_balance = 0
  • start_index = 3

Since total balance is non-negative, station 3 is the answer.

Example 2

gas  = [2,3,4]
cost = [3,4,3]
Index Gas Cost Difference Current Balance Total Balance Start Index
0 2 3 -1 -1 -1 0
Reset 0 -1 1
1 3 4 -1 -1 -2 1
Reset 0 -2 2
2 4 3 1 1 -1 2

Final values:

  • total_balance = -1

Since total gas is smaller than total cost, completing the circuit is impossible.

Return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each station is processed exactly once
Space O(1) Only a few integer variables are used

The algorithm performs a single linear scan across the arrays. No nested loops or additional data structures are needed.

Although candidate starting stations change during traversal, each index is still visited only once, giving true linear complexity.

Space usage remains constant because the algorithm stores only running totals and indices.

Test Cases

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total_balance = 0
        current_balance = 0
        start_index = 0

        for i in range(len(gas)):
            difference = gas[i] - cost[i]

            total_balance += difference
            current_balance += difference

            if current_balance < 0:
                start_index = i + 1
                current_balance = 0

        if total_balance < 0:
            return -1

        return start_index

solution = Solution()

assert solution.canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2]) == 3
# Standard example with valid solution

assert solution.canCompleteCircuit([2,3,4], [3,4,3]) == -1
# Standard example with impossible route

assert solution.canCompleteCircuit([5], [4]) == 0
# Single station, enough gas

assert solution.canCompleteCircuit([2], [3]) == -1
# Single station, insufficient gas

assert solution.canCompleteCircuit([0,0,0], [0,0,0]) == 0
# All zeros

assert solution.canCompleteCircuit([3,1,1], [1,2,2]) == 0
# Valid start at index 0

assert solution.canCompleteCircuit([1,2,3], [3,1,2]) == 1
# Valid start after early failure

assert solution.canCompleteCircuit([6,1,4,3,5], [3,8,2,4,2]) == 2
# Multiple resets before finding solution

assert solution.canCompleteCircuit([4,5,2,6,5,3], [3,2,7,3,2,9]) == -1
# Total gas less than total cost

assert solution.canCompleteCircuit([10,1,1,1], [1,3,3,3]) == 0
# Large surplus at first station
Test Why
[1,2,3,4,5], [3,4,5,1,2] Standard successful case
[2,3,4], [3,4,3] Standard impossible case
[5], [4] Single-element success
[2], [3] Single-element failure
[0,0,0], [0,0,0] Zero values everywhere
[3,1,1], [1,2,2] Start index is zero
[1,2,3], [3,1,2] Requires resetting candidate start
[6,1,4,3,5], [3,8,2,4,2] Multiple failed intervals
[4,5,2,6,5,3], [3,2,7,3,2,9] Global impossibility check
[10,1,1,1], [1,3,3,3] Large early surplus

Edge Cases

Total Gas Is Less Than Total Cost

A common mistake is attempting to simulate routes without first checking whether the journey is globally possible.

For example:

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

The total gas is 9, while the total cost is 12. No starting point can ever succeed.

The implementation handles this naturally using total_balance. If the final balance is negative, the algorithm immediately returns -1.

Single Station Arrays

Arrays of length 1 are easy to mishandle due to circular traversal assumptions.

For example:

gas = [5]
cost = [4]

The answer should be 0 because the car can leave and return to the same station successfully.

The algorithm works correctly because the loop processes the single station normally, and the balance remains non-negative.

Multiple Consecutive Failed Starts

Consider:

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

Starting at index 0 fails immediately. Starting at 1 also fails.

A naive implementation might retry every station individually, leading to quadratic complexity.

The greedy solution avoids this inefficiency by proving that once a segment fails, every station within that failed segment is invalid. It skips directly to the next possible candidate, preserving linear runtime.