3.16 Gas Station

3.16.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 134
• Difficulty: Medium
• URL: https://leetcode.com/problems/gas-station/
• Tags: NeetCode 150
• Techniques: Greedy Array

3.16.2 Description

There are n gas stations along a circular route, where the amount of gas at the i-th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i-th station to its next (i + 1)-th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

3.16.3 Examples

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

3.16.4 Constraints

• n == gas.length == cost.length
• \(1 \le n \le 10^5\)
• \(0 \le gas[i], cost[i] \le 10^4\)

3.16.5 Solution - Greedy One Pass

3.16.5.1 Walkthrough

This solution uses a greedy one-pass algorithm to find the starting gas station index.

Core Strategy:

The problem has two critical insights:

1. Existence Check: If the total gas is less than total cost, completing the circuit is impossible
   • sum(gas) < sum(cost) → return -1
   • This can be checked by tracking gasTotalRemained = sum(gas[i] - cost[i])
2. Greedy Starting Point Selection: If starting from index startIdx, we fail at index i (running balance goes negative), then no index between startIdx and i (inclusive) can be a valid starting point

Why Can’t Indices Between startIdx and i Work?

Suppose we start at startIdx and fail at i:

Balance from startIdx to i: B[startIdx→i] < 0 (we ran out of gas)

Now consider any intermediate index k where startIdx < k ≤ i:

Balance from k to i: B[k→i] = B[startIdx→i] - B[startIdx→k-1]

Since we successfully reached k from startIdx, we know B[startIdx→k-1] ≥ 0.

Therefore:

B[k→i] = B[startIdx→i] - B[startIdx→k-1]
       ≤ B[startIdx→i] (since we subtract a non-negative value)
       < 0

This proves that starting from k would fail even earlier than starting from startIdx! Thus, we can safely skip all indices from startIdx to i and restart from i + 1.

Visual Example Walkthrough:

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

Compute net gain at each station: gas[i] - cost[i]
Index:     0    1    2    3    4
Net:      -2   -2   -2   +3   +3

Step-by-step execution:

i=0: net=-2
  gasAccRemained = 0 + (-2) = -2 (negative!)
  gasTotalRemained = -2
  Failed at i=0, reset: startIdx = 1, gasAccRemained = 0

i=1: net=-2
  gasAccRemained = 0 + (-2) = -2 (negative!)
  gasTotalRemained = -2 + (-2) = -4
  Failed at i=1, reset: startIdx = 2, gasAccRemained = 0

i=2: net=-2
  gasAccRemained = 0 + (-2) = -2 (negative!)
  gasTotalRemained = -4 + (-2) = -6
  Failed at i=2, reset: startIdx = 3, gasAccRemained = 0

i=3: net=+3
  gasAccRemained = 0 + 3 = 3 (positive, keep going!)
  gasTotalRemained = -6 + 3 = -3
  startIdx = 3

i=4: net=+3
  gasAccRemained = 3 + 3 = 6 (still positive!)
  gasTotalRemained = -3 + 3 = 0
  startIdx = 3

Final check:
  gasTotalRemained = 0 (not negative, solution exists!)
  Return startIdx = 3 ✓

Why This Greedy Approach is Optimal:

• No need to check circular completion: If gasTotalRemained ≥ 0 and we found a valid startIdx that doesn’t fail in the forward pass, it’s guaranteed to complete the circuit
• Proof: The only way to fail would be if total gas < total cost, but we already checked that condition
• One pass suffices: We eliminate all invalid starting points greedily without backtracking

3.16.5.2 Analysis

• Time Complexity: O(n)
  • Single pass through the array
  • Each station is visited exactly once
  • Constant-time operations per station
  • This is optimal since we must examine all stations
• Space Complexity: O(1)
  • Only uses three integer variables (gasTotalRemained, gasAccRemained, startIdx)
  • No additional data structures
  • This is optimal for the problem

Why This Approach is Optimal: - We cannot do better than O(n) time since we must check if total gas \(\ge\) total cost - The greedy property eliminates the need for O(n²) brute force checking all starting points

3.16.5.3 Implementation Steps

Initialization: 1. Set startIdx = 0 (candidate starting position) 2. Set gasAccRemained = 0 (fuel balance from current starting point) 3. Set gasTotalRemained = 0 (total fuel balance for existence check)

Main Loop (iterate through all stations):

For each station i from 0 to n-1:

4. Update both trackers:
   • Compute net gain: net = gas[i] - cost[i]
   • Update running balance: gasAccRemained += net
   • Update total balance: gasTotalRemained += net
5. Check if current starting point fails:
   • If gasAccRemained < 0:
     • Current starting point is invalid
     • Greedy choice: Reset startIdx = i + 1 (skip all indices from old start to i)
     • Reset gasAccRemained = 0 (start fresh from new candidate)

Final Check:

6. Verify solution exists:
   • If gasTotalRemained < 0: No solution possible, return -1
   • Otherwise: Return startIdx (guaranteed to be valid)

3.16.5.4 Code - Java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int gasTotalRemained = 0;
        int gasAccRemained = 0;
        int startIdx = 0;

        for (int i = 0; i < len; i++) {
            gasAccRemained += gas[i] - cost[i];
            gasTotalRemained += gas[i] - cost[i];

            // If starting from startIdx, we fail at index i (cumulative sum goes negative),
            // then no index between startIdx and i can be a valid starting point
            if (gasAccRemained < 0) {
                startIdx = i + 1;
                gasAccRemained = 0;
            }
        }

        if (gasTotalRemained < 0) {
            return -1;
        }

        return startIdx;
    }
}

3.16.5.5 Code - Golang

func canCompleteCircuit(gas []int, cost []int) int {
    gasTotalRemained := 0
    gasAccuRemained := 0
    startIndex := 0

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

        // If starting from startIndex, we fail at index i (cumulative sum goes negative),
        // then no index between startIndex and i can be a valid starting point
        if gasAccuRemained < 0 {
            startIndex = i + 1
            gasAccuRemained = 0
        }
    }

    if gasTotalRemained < 0 {
        return -1
    }

    return startIndex
}