Gas Station

134.Gas Station

Array

Greedy

Problem Statement:

There are n gas stations along a circular route. You have a car with an unlimited gas tank that can only travel clockwise. At each station i, you can collect gas[i] amount of gas and it costs cost[i] to travel to the next station. Find the starting station where you can complete the circuit, or return -1 if impossible.

Example:

Input:

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

→

Output:

3

Starting at station 3, you can complete the circuit. Station 3 → 4 → 0 → 1 → 2 → 3

Key Insights:

1. If total gas is greater than or equal to total cost, a solution exists
2. If you can't reach station i from station j, you can't reach i from any station between j and i
3. Solution is guaranteed to be unique if it exists

Algorithm:

1. Track total gas-cost difference to determine if solution exists
2. Track current sum of gas-cost differences
   • If it becomes negative, current path is invalid
   • Reset sum to 0 and start from next station
3. If total ≥ 0, return the last start point tried
4. Otherwise, return -1

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0;      // Track if solution exists
    int currSum = 0;     // Track current path
    int start = 0;       // Potential starting point

    // If we can't get to next station, next station becomes the start
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;    // Track overall gas-cost difference
        currSum += diff;  // Track current path difference
        
        // If we can't reach next station
        if (currSum < 0) {
            start = i + 1;  // Try starting from next station
            currSum = 0;    // Reset current path
        }
    }
    
    // If total gas >= total cost, solution exists at 'start'
    return total >= 0 ? start : -1;
}

Python Solution:

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
    total = curr_sum = start = 0
    
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff      # Track if solution exists
        curr_sum += diff   # Track current path
        
        if curr_sum < 0:    # Can't reach next station
            start = i + 1  # Try starting from next station
            curr_sum = 0   # Reset path
    
    return start if total >= 0 else -1

C++ Solution:

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, curr_sum = 0, start = 0;
    
    for (int i = 0; i < gas.size(); i++) {
        int diff = gas[i] - cost[i];
        total += diff;     // Track overall difference
        curr_sum += diff;  // Track current path
        
        if (curr_sum < 0) {
            start = i + 1;  // Try next station
            curr_sum = 0;   // Reset path
        }
    }
    
    return total >= 0 ? start : -1;
}