Gas Station

Problem Statement

You’re on a circular road trip with a car that has a limited gas tank. Given two arrays—gas (amount of gas at each station) and cost (gas needed to travel to the next station)—determine the starting station index from which you can complete the circuit. If it’s impossible, return -1. This medium-level greedy challenge tests your ability to optimize your fuel strategy, ensuring you never run dry as you loop back to your starting point!

Example

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

Output: 3 (start at station 3: net gas = 4-1=3, 5-2=3, 1-3=-2, 2-4=-2, 3-5=-2, but total gas ≥ total cost)

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

Output: -1 (no starting point allows completion: total gas = 9, total cost = 10)

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

Output: 4 (start at station 4: completes circuit with careful gas tracking)

Code

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0;    // Total gas - cost balance
        int currTank = 0;     // Current gas tank
        int startStation = 0; // Starting station index
        
        for (int i = 0; i < gas.length; i++) {
            totalTank += gas[i] - cost[i];
            currTank += gas[i] - cost[i];
            
            // If current tank is negative, reset start to next station
            if (currTank < 0) {
                startStation = i + 1;
                currTank = 0;
            }
        }
        
        // If total gas is less than total cost, impossible
        return totalTank >= 0 ? startStation : -1;
    }
}
            

def can_complete_circuit(gas, cost):
    total_tank = 0    # Total gas - cost balance
    curr_tank = 0     # Current gas tank
    start_station = 0 # Starting station index
    
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        curr_tank += gas[i] - cost[i]
        
        # If current tank is negative, reset start to next station
        if curr_tank < 0:
            start_station = i + 1
            curr_tank = 0
    
    # If total gas is less than total cost, impossible
    return start_station if total_tank >= 0 else -1

# Example usage
print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 3
print(can_complete_circuit([2, 3, 4], [3, 4, 3]))              # -1
print(can_complete_circuit([5, 1, 2, 3, 4], [4, 4, 1, 5, 1])) # 4
            

function canCompleteCircuit(gas, cost) {
    let totalTank = 0;    // Total gas - cost balance
    let currTank = 0;     // Current gas tank
    let startStation = 0; // Starting station index
    
    for (let i = 0; i < gas.length; i++) {
        totalTank += gas[i] - cost[i];
        currTank += gas[i] - cost[i];
        
        // If current tank is negative, reset start to next station
        if (currTank < 0) {
            startStation = i + 1;
            currTank = 0;
        }
    }
    
    // If total gas is less than total cost, impossible
    return totalTank >= 0 ? startStation : -1;
}

// Example usage
console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 3
console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3]));             // -1
console.log(canCompleteCircuit([5, 1, 2, 3, 4], [4, 4, 1, 5, 1])); // 4
            

Explanation

• Greedy Strategy: Test each station as a starting point, but optimize by skipping stations once the tank goes negative.
• Single Pass: Track total gas-cost balance and current tank, resetting the start when current tank depletes.
• Key Insight: If total gas ≥ total cost, there’s a solution; the start is where we recover from deficits.
• Flow Example (gas=[1,2,3,4,5], cost=[3,4,5,1,2]): Start at 0 fails (1-3=-2), try 3 (4-1=3, 5-2=3, etc.), completes with total ≥ 0.
• Termination: Return start if feasible, -1 if total gas < total cost.

Note