Code Implementation

class Solution:
    def canCompleteCircuit(self, gas, cost):
        total_tank = 0
        curr_tank = 0
        start_station = 0
        for i in range(len(gas)):
            total_tank += gas[i] - cost[i]
            curr_tank += gas[i] - cost[i]
            if curr_tank < 0:
                start_station = i + 1
                curr_tank = 0
        return start_station if total_tank >= 0 else -1
      

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total_tank = 0, curr_tank = 0, start_station = 0;
        for (int i = 0; i < gas.size(); ++i) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            if (curr_tank < 0) {
                start_station = i + 1;
                curr_tank = 0;
            }
        }
        return total_tank >= 0 ? start_station : -1;
    }
};
      

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0, currTank = 0, startStation = 0;
        for (int i = 0; i < gas.length; ++i) {
            totalTank += gas[i] - cost[i];
            currTank += gas[i] - cost[i];
            if (currTank < 0) {
                startStation = i + 1;
                currTank = 0;
            }
        }
        return totalTank >= 0 ? startStation : -1;
    }
}
      

var canCompleteCircuit = function(gas, cost) {
    let totalTank = 0, currTank = 0, startStation = 0;
    for (let i = 0; i < gas.length; ++i) {
        totalTank += gas[i] - cost[i];
        currTank += gas[i] - cost[i];
        if (currTank < 0) {
            startStation = i + 1;
            currTank = 0;
        }
    }
    return totalTank >= 0 ? startStation : -1;
};
      

Problem Description

You are given two integer arrays, gas and cost, each of length n. The i-th gas station has gas[i] units of gas available. It costs cost[i] units of gas to travel from station i to station i+1 (the last station connects to the first, forming a circle).

Your task is to determine the starting gas station index from which you can travel around the circuit once in the clockwise direction, visiting every station exactly once and returning to the starting point, without ever running out of gas. If it is not possible, return -1.

• There is exactly one unique solution if a solution exists.
• You may assume the car starts with an empty tank, but can refuel at each station.
• You cannot skip stations or refuel at non-station points.

Thought Process

At first glance, it might seem that we need to try starting at every station and simulate the trip, which would be a brute-force approach. For each starting index, we would check if we can make a full circle without running out of gas. However, this would be slow for large inputs.

On closer inspection, we realize that the problem is really about whether, at any point, the total gas collected so far is enough to cover the cost to the next station. If the total amount of gas is less than the total cost, it is impossible to complete the circuit from any station.

The challenge is to find the correct starting station efficiently. If we ever run out of gas at a certain station, it means that none of the stations between our previous starting point and this station can be the answer, so we can skip them.

Solution Approach

• Step 1: Initialize three variables: total_tank (to track the overall gas surplus/deficit), curr_tank (to track the gas balance since the last starting point), and start_station (to record the current candidate starting station).
• Step 2: Iterate over all stations:
  • At each station i, add gas[i] - cost[i] to both total_tank and curr_tank.
  • If curr_tank becomes negative, it means we can't reach station i+1 from our current start_station. Therefore, we set start_station to i+1 and reset curr_tank to zero.
• Step 3: After the loop, if total_tank is negative, it means the total gas is less than the total cost, so return -1.
• Step 4: Otherwise, return start_station as the answer.

This approach is efficient because it only needs one pass through the arrays and skips unnecessary checks by leveraging the fact that if you can't reach a station from a certain segment, none of the stations in that segment can be a valid start.

Example Walkthrough

Let's take gas = [1,2,3,4,5] and cost = [3,4,5,1,2].

1. Start at station 0:
   • curr_tank = 1-3 = -2 (can't reach station 1)
   • So, set start_station = 1, curr_tank = 0
2. At station 1:
   • curr_tank = 0 + 2-4 = -2 (can't reach station 2)
   • Set start_station = 2, curr_tank = 0
3. At station 2:
   • curr_tank = 0 + 3-5 = -2 (can't reach station 3)
   • Set start_station = 3, curr_tank = 0
4. At station 3:
   • curr_tank = 0 + 4-1 = 3
5. At station 4:
   • curr_tank = 3 + 5-2 = 6
6. After the loop, total_tank = (1-3)+(2-4)+(3-5)+(4-1)+(5-2) = -2-2-2+3+3 = 0
7. Since total_tank >= 0, the answer is start_station = 3.

Thus, starting at station 3 allows you to complete the circuit.

Time and Space Complexity

• Brute-force approach: For each station, simulate the trip around the circuit. This is O(n²) time and O(1) space, since for each of n stations, you may have to go through up to n stations.
• Optimized approach (above): Only one pass through the arrays is needed, so the time complexity is O(n) and space complexity is O(1), since we only use a few integer variables regardless of input size.

Summary

The Gas Station problem can be solved efficiently by realizing that if you can't reach a certain station from your current start, none of the stations in between can be valid starting points. By keeping track of the total gas surplus or deficit and resetting the starting point whenever you run out of gas, you find the unique solution in linear time. This approach is both elegant and efficient, leveraging problem constraints and cumulative logic to avoid unnecessary work.