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 circular route 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. Your tank = 5 - 5 + 4 = 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 travel around the circuit once.

Steps

1. Calculate total gas and total cost: If the total gas is less than the total cost, it's impossible to complete the circle, return -1.

2. Greedy approach: Iterate through the gas stations. Keep track of the current tank's gas level (tank) and the total gas surplus (surplus) from the starting point.

3. Check for negative surplus: If at any point surplus becomes negative, it means we can't reach the current station from the starting point. Reset the starting point to the next station, and reset tank and surplus.

4. Return starting point: After iterating through all stations, the last starting point will be the solution.

Explanation

The key insight is that if a solution exists, it's unique. The greedy approach works because if we find a point where the surplus becomes negative, that means any starting point before this point also cannot reach the end. We only need to explore points after the negative surplus point as a potential starting point. The algorithm ensures that we always have enough gas to reach the next station.

Code

public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.Length;
        long totalGas = 0;
        long totalCost = 0;

        for (int i = 0; i < n; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
        }

        if (totalGas < totalCost) return -1; // Impossible to complete the circuit

        int start = 0;
        long tank = 0;
        long surplus = 0;

        for (int i = 0; i < n; i++) {
            tank += gas[i] - cost[i];
            surplus += gas[i] - cost[i];
            if (surplus < 0) {
                start = i + 1;
                tank = 0;
                surplus = 0;
            }
        }

        return start;
    }
}

Complexity

• Time Complexity: O(n), where n is the number of gas stations. We iterate through the array at most twice.
• Space Complexity: O(1). We use a constant amount of extra space.