Gas Station

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

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith 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.

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.

Constraints:

• n == gas.length == cost.length
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104
• The input is generated such that the answer is unique.

Approach: Greedy with Total and Current Balance

Algorithm

1. If the total gas is less than the total cost, no valid starting station exists; return -1
2. Otherwise, iterate through stations maintaining a running balance (currentGas)
3. If the balance ever becomes negative at station i, reset the balance to 0 and set the candidate start to i + 1
4. Return the final candidate start

Time & Space Complexity

• Time Complexity: O(n) - single pass through the arrays
• Space Complexity: O(1) - constant extra space

Java Implementation

public class GasStation {

    /**
     * Return the starting gas station index to complete the circuit.
     * @param gas Amount of gas at each station
     * @param cost Cost to travel to the next station
     * @return Starting index or -1 if no solution exists
     */
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int currentGas = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i] - cost[i];
            currentGas += gas[i] - cost[i];

            // Cannot reach station i + 1 from this start
            if (currentGas < 0) {
                start = i + 1;
                currentGas = 0;
            }
        }

        return totalGas >= 0 ? start : -1;
    }

    // Test method
    public static void main(String[] args) {
        int[] gas1 = {1, 2, 3, 4, 5};
        int[] cost1 = {3, 4, 5, 1, 2};
        System.out.println("Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]");
        System.out.println("Output: " + canCompleteCircuit(gas1, cost1)); // Expected: 3

        int[] gas2 = {2, 3, 4};
        int[] cost2 = {3, 4, 3};
        System.out.println("Input: gas = [2,3,4], cost = [3,4,3]");
        System.out.println("Output: " + canCompleteCircuit(gas2, cost2)); // Expected: -1
    }
}

Example Walkthrough

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

1. i=0: currentGas = 1-3 = -2 < 0, reset. start=1, currentGas=0. totalGas=-2
2. i=1: currentGas = 2-4 = -2 < 0, reset. start=2, currentGas=0. totalGas=-4
3. i=2: currentGas = 3-5 = -2 < 0, reset. start=3, currentGas=0. totalGas=-6
4. i=3: currentGas = 4-1 = 3. totalGas=-3
5. i=4: currentGas = 3+3 = 6. totalGas=0

totalGas >= 0, return start = 3.

Key Points

1. Feasibility Check: If totalGas < totalCost, no tour exists
2. Greedy Reset: If the running balance drops below zero at station i, stations 0 through i cannot be valid starts; try i + 1
3. Unique Solution: The problem guarantees at most one valid start
4. Single Pass: O(n) time with O(1) space
5. Intuition: A valid start can be found greedily after the last point where the balance went negative