Gas Station medium

Problem Statement

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

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

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note: If solution is possible, there is only one unique solution.

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 = 3 Travel to station 0. Your tank = 3 + 5 = 8 Travel to station 1. Your tank = 8 - 3 = 5 Travel to station 2. Your tank = 5 + 2 = 7 Travel to station 3. Your tank = 7 - 5 = 2 Travel to station 4. Your tank = 2 + 4 =6 Travel to station 0. Your tank = 6 - 2 = 4

Example 2

Input: gas = [2,3,4], cost = [3,4,3] Output: -1 Explanation: You can't start at station 0 or 1 or 2 to complete the circuit.

Steps

1. Calculate the net gain at each station: For each station i, calculate gas[i] - cost[i]. This represents the net gain (or loss) in gas after visiting that station.

2. Find a potential starting point: Iterate through the stations. If at any point the cumulative net gain becomes negative, this means you can't start at any of the previous stations. Reset the cumulative net gain and the potential starting point.

3. Check the feasibility: Once you've iterated through all the stations, check if the final cumulative net gain is non-negative. If it's negative, there's no solution. Otherwise, the last potential starting point you identified is the solution.

Explanation

The key insight is that if a solution exists, there's only one. The algorithm leverages this fact. If the cumulative net gain becomes negative at any point, it signifies that you cannot start at any of the previously visited stations. Why? Because you'd run out of gas before completing the circle. Therefore, the next station becomes a potential starting point. The only way you can complete the circuit is if, after visiting all stations, your total net gain is non-negative.

Code

function canCompleteCircuit(gas: number[], cost: number[]): number {
    const n = gas.length;
    let total_surplus = 0;
    let surplus = 0;
    let starting_station = 0;

    for (let i = 0; i < n; i++) {
        const diff = gas[i] - cost[i];
        total_surplus += diff;
        surplus += diff;

        if (surplus < 0) {
            surplus = 0;
            starting_station = i + 1;
        }
    }

    return total_surplus >= 0 ? starting_station : -1;
};

Complexity

• Time Complexity: O(n), where n is the number of gas stations. We iterate through the array once.
• Space Complexity: O(1). We use only a few constant extra variables.