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.

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 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 gain (or loss) of gas if you start at that station and move to the next.

2. Check for a feasible solution: A solution exists only if the total net gain across all stations is non-negative. If it's negative, there's no way to complete the circuit.

3. Find the starting station: Iterate through the stations. Maintain a current_tank variable to track the current gas level. If current_tank ever goes negative, reset current_tank to 0 and start a new attempt from the next station. The index where you successfully complete the circuit is the solution.

Explanation:

The intuition behind this approach is based on the fact that if the total net gain is negative, there's no way to make a full circle. If the total net gain is positive, there must be a starting point where you can successfully complete the circuit. We don't need to check every possible starting point exhaustively; instead, the algorithm cleverly uses the current_tank to efficiently find the solution. If we encounter a negative current_tank, it indicates that we can't reach the next station from the current starting point, so we need to try a new starting point.

Code:

#include <vector>

class Solution {
public:
    int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
        int n = gas.size();
        int total_net_gain = 0;
        int current_tank = 0;
        int start_station = 0;

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

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

        return (total_net_gain >= 0) ? start_station : -1;
    }
};

Complexity:

• Time Complexity: O(n), where n is the number of gas stations. We iterate through the stations twice (once to calculate the total net gain and once to find the starting station).
• Space Complexity: O(1). We use only a few constant extra variables.