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

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 - 3 = 3 Travel to station 1. Your tank = 3 + 1 = 4 Travel to station 2. Your tank = 4 - 4 = 0 Travel to station 3. Your tank = 0 + 2 = 2 The final tank is 2 >0. This is the correct solution.

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 in the clockwise direction.

Steps

1. Calculate the net gain at each station: For each station i, calculate gas[i] - cost[i]. This represents the net amount of gas you gain after visiting that station.

2. Find a potential starting point: Iterate through the stations. Keep track of the current tank's fuel level (current_tank) and the total net gain (total_net_gain). If current_tank becomes negative at any point, it means you can't reach the next station from the current starting point. Reset current_tank to 0 and start checking from the next station.

3. Check if a solution exists: If total_net_gain is negative after iterating through all stations, there's no solution. Otherwise, the last station where you reset current_tank is the solution (or the starting station).

Explanation

The key insight is that if the total net gain of gas across all stations is negative, it's impossible to complete the circular route. If the total net gain is non-negative, there must be at least one starting point that allows completion of the route. The algorithm efficiently finds that starting point. We reset current_tank when it goes negative because there is no way to reach the next station from the current start point.

Code

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int current_tank = 0;
        int total_net_gain = 0;
        int starting_station = 0;

        for (int i = 0; i < n; i++) {
            int net_gain = gas[i] - cost[i];
            current_tank += net_gain;
            total_net_gain += net_gain;

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

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

Complexity

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