Gas Station

LeetCode 134: Gas Station Solution & Explanation

Problem Overview

TL;DR: Iterate through the stations once, tracking the current fuel balance; if the balance drops below zero, the starting point must be after the current station, so reset the start index and clear the current balance.

In the LeetCode 134 Gas Station problem, you are given two integer arrays, gas and cost. gas[i] represents the fuel available at the $i$-th station, and cost[i] represents the fuel required to travel from station $i$ to station $i+1$. The route is circular. Your goal is to find the index of the starting gas station that allows you to traverse the entire circuit once without running out of fuel. If no such station exists, return -1.

This is a classic interview question that tests your ability to optimize a simulation process using greedy logic.

Brute Force Approach for Gas Station

The most intuitive way to solve this is to simulate the journey starting from every single station. We treat every index $i$ from $0$ to $n-1$ as a potential starting point and attempt to complete the circle.

Naive Algorithm Steps

1. Iterate through each station $i$ from $0$ to $n-1$.
2. For each start station $i$, initialize a tank variable to 0.
3. Use an inner loop to simulate the travel to the next $n$ stations (using modulo arithmetic to handle the circular array).
4. At each step, update the tank: tank += gas[current] - cost[current].
5. If tank becomes negative at any point, break the inner loop (this start index is invalid).
6. If the inner loop completes $n$ steps successfully, return $i$.

Pseudo-code

for start from 0 to n-1:
    tank = 0
    possible = true
    for step from 0 to n-1:
        current = (start + step) % n
        tank += gas[current] - cost[current]
        if tank < 0:
            possible = false
            break
    if possible:
        return start
return -1

Complexity Analysis

The time complexity is $O(N^2)$ because for every station, we iterate through the entire array in the worst case. With $N$ up to $10^5$, $N^2$ operations result in $10^{10}$ computations, which far exceeds the standard time limit of roughly $10^8$ operations per second. This approach will result in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Greedy Patterns

We utilize the insights above to solve the problem in a single pass.

1. Track Global Balance: We maintain a total_surplus variable that sums gas[i] - cost[i] for all $i$. This determines if a solution exists at all.
2. Track Current Segment: We maintain a current_surplus variable. As we iterate, we add gas[i] - cost[i] to it.
3. Greedy Choice: If current_surplus drops below 0, it means the current starting point (and any point between the start and the current index) is invalid.
4. Reset: We reset the starting candidate to i + 1 and reset current_surplus to 0. We do not need to re-check previous stations.

This approach ensures we touch every element exactly once.

Execution Flow

1. Initialize total_surplus to 0.
2. Initialize current_surplus to 0.
3. Initialize start_index to 0.
4. Iterate through the array with index i from 0 to n-1:
   • Calculate the net gain at station i: balance = gas[i] - cost[i].
   • Add balance to total_surplus.
   • Add balance to current_surplus.
   • Check Constraint: If current_surplus < 0:
     • The current path failed. The start cannot be start_index or any index up to i.
     • Update start_index = i + 1.
     • Reset current_surplus = 0 (empty tank for the new potential start).
5. After the loop finishes:
   • Check total_surplus. If it is less than 0, return -1.
   • Otherwise, return start_index.

Proof of Correctness

Claim: If total_surplus >= 0, the start_index identified by the greedy algorithm allows traversal of the full circle.

Proof: Since total_surplus >= 0, a solution exists. The algorithm sets start_index to $k$. This implies that for any segment ending before $k$, the sum was negative, causing a reset. However, starting from $k$, the current_surplus never dropped below zero until the end of the array (index $n-1$). The remaining question is: can we wrap around from $n-1$ back to $k$? Because total_surplus is the sum of the segment $[0, k-1]$ and the segment $[k, n-1]$, and we know total_surplus >= 0, the positive surplus accumulated in $[k, n-1]$ must be sufficient to offset the negative deficit accumulated in $[0, k-1]$. Therefore, the tank will remain non-negative after wrapping around.

Pattern Reuse Notes

The logic used in the LeetCode 134 Solution is a specific application of greedy accumulation, sharing similarities with:

• Maximum Subarray Sum (Kadane's Algorithm): Kadane's algorithm also resets the current running sum when it drops below zero (or when the current element is greater than the running sum, depending on implementation). Both problems involve finding a valid "segment" in a linear array based on cumulative sums.

Reference Implementation

C++ Solution for LeetCode 134

1class Solution {
2public:
3    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
4        int total_surplus = 0;
5        int current_surplus = 0;
6        int start_index = 0;
7        
8        for (int i = 0; i < gas.size(); ++i) {
9            int balance = gas[i] - cost[i];
10            total_surplus += balance;
11            current_surplus += balance;
12            
13            // If the tank becomes empty, we cannot start at 'start_index'
14            // or any station between 'start_index' and 'i'.
15            if (current_surplus < 0) {
16                current_surplus = 0;
17                start_index = i + 1;
18            }
19        }
20        
21        // If total gas is less than total cost, a round trip is impossible.
22        return (total_surplus < 0) ? -1 : start_index;
23    }
24};

Java Solution for LeetCode 134

1class Solution {
2    public int canCompleteCircuit(int[] gas, int[] cost) {
3        int totalSurplus = 0;
4        int currentSurplus = 0;
5        int startIndex = 0;
6        
7        for (int i = 0; i < gas.length; i++) {
8            int balance = gas[i] - cost[i];
9            totalSurplus += balance;
10            currentSurplus += balance;
11            
12            // If current tank drops below zero, the current start point is invalid.
13            // Reset start point to the next station.
14            if (currentSurplus < 0) {
15                currentSurplus = 0;
16                startIndex = i + 1;
17            }
18        }
19        
20        // If the total gas provided is less than total cost, return -1
21        return (totalSurplus < 0) ? -1 : startIndex;
22    }
23}

Python Solution for LeetCode 134

1class Solution:
2    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
3        total_surplus = 0
4        current_surplus = 0
5        start_index = 0
6        
7        for i in range(len(gas)):
8            balance = gas[i] - cost[i]
9            total_surplus += balance
10            current_surplus += balance
11            
12            # If tank goes below zero, the path from start_index to i is invalid
13            if current_surplus < 0:
14                current_surplus = 0
15                start_index = i + 1
16        
17        # If total gas available < total gas required, impossible to complete circuit
18        return start_index if total_surplus >= 0 else -1