Gas Station

Concept

LeetCode #134.
Problem: There are n gas stations along a circular route. You are given two integer arrays gas and cost. gas[i] is the amount of gas at the i-th station. cost[i] is the cost to travel from the i-th station to the next. Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

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

You start with an empty tank.
If you start at index 0, you gain 1 gas. It costs 3 to travel. 1 - 3 = -2. You crash. Index 0 fails.
If you start at index 3, you gain 4 gas. It costs 1. You arrive at index 4 with 3 gas in the tank. You gain 5 gas… you successfully make the loop! Output: 3.

The Brute Force Approach ($O(N^2)$)

You could just loop through every single index from 0 to n. For each index, you run a secondary while loop that simulates driving the car in a circle. If the car crashes, you break and try starting at the next index.
This works, but takes $O(N^2)$ time.

The Greedy Mathematical Guarantees ($O(N)$)

To solve this in $O(N)$ time, you must rely on two brilliant mathematical observations:

Guarantee 1 (Global Suitability):
If the total sum of all gas in the entire world is less than the total sum of all cost in the world, completing the circle is mathematically impossible. Return -1. If Total Gas >= Total Cost, the math guarantees that a valid starting point MUST exist.

Guarantee 2 (The Greedy Elimination):
If you start driving at Station A, successfully pass Station B, and then crash at Station C (your tank drops below zero), it is impossible for ANY station between A and C to be the correct starting point.
Why? Because Station A successfully fed you gas. If you couldn’t make it to C even with the bonus gas from A, you definitely won’t make it to C starting from B with an empty tank!
Therefore, if you crash at C, the next logically possible starting point is Station C + 1.

Implementation

// Time Complexity: O(N) (One single pass)
// Space Complexity: O(1)

function canCompleteCircuit(gas: number[], cost: number[]): number {
    let totalGas = 0;
    let totalCost = 0;
    
    let currentTank = 0;
    let startingIndex = 0;

    for (let i = 0; i < gas.length; i++) {
        // Tally the global sums
        totalGas += gas[i];
        totalCost += cost[i];

        // Simulate driving
        currentTank += gas[i] - cost[i];

        // Did we crash?
        if (currentTank < 0) {
            // Guarantee 2: A->C failed. The next possible start is i + 1!
            startingIndex = i + 1;
            
            // Reset our tank to empty for the new attempt
            currentTank = 0;
        }
    }

    // Guarantee 1: Check if the route is mathematically impossible
    if (totalGas < totalCost) {
        return -1;
    }

    // If it's mathematically possible, our startingIndex is guaranteed to be correct!
    return startingIndex;
}

Why does this work without looping back?

The hardest part to grasp is why we don’t need a second pass to simulate the circle wrapping around the end of the array back to the start.

Look at the logic:

1. totalGas >= totalCost guarantees a solution exists.
2. The for loop finds a startingIndex that successfully reaches the very end of the array (length - 1) without crashing.
3. If a solution is guaranteed to exist, and our startingIndex successfully made it to the end of the array, the mathematical laws of the universe guarantee that the gas accumulated during that final push will perfectly cover any deficit required to wrap around and reach the startingIndex again.

Because of the math, the simulation is completely unnecessary!

Interview Questions

Q: Can there be multiple valid starting points?
A: The LeetCode problem explicitly states: “If there exists a solution, it is guaranteed to be unique.” If multiple solutions were allowed, this specific greedy algorithm would simply return the first valid starting point it finds moving left-to-right.

Q: A junior developer suggests calculating totalGas and totalCost in a separate initial for loop to abort early if it’s impossible. Is this a good idea?
A: Functionally, it is perfectly fine and still $O(N)$ time. However, it requires iterating through the arrays twice ($O(2N)$). Combining the global tally and the local simulation into a single for loop is considered more optimal and mathematically elegant.