134. Gas Station

Intuition

To solve this problem, we need to determine if there exists a starting gas station from which we can complete the entire circular route without running out of gas. The key insight is that if the total amount of gas is greater than or equal to the total cost, then a solution must exist. Additionally, if we fail to complete the journey from a certain starting point, it means that any starting point between that failed point and our current position is also invalid.

Approach

1. Initialize Variables: - total to track the total net gas (total gas - total cost). - cur to track the current net gas from the current starting point. - start to record the starting index.
2. Iterate Through the Gas Stations: - For each gas station, calculate the net gas by subtracting cost[i] from gas[i]. - Add this net gas to both total and cur. - If cur becomes negative, it means we cannot complete the journey starting from the current start. So, we update start to i + 1 and reset cur to 0.
3. Determine the Result: - After iterating through all gas stations, if total is negative, return -1 because it is impossible to complete the circuit. - Otherwise, return start as the valid starting index.

Complexity

• Time Complexity: O(n), where n is the number of gas stations. We only make a single pass through the gas and cost arrays.
• Space Complexity: O(1), as we only use a few extra variables for the computation.

Code

C++

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
        int total = 0;
        int cur = 0;
        int start = 0;
        
        for (int i = 0; i < gas.size(); i++) {
            int netCost = gas[i] - cost[i];
            total += netCost;
            cur += netCost;
            if (cur < 0) {
                start = i + 1;
                cur = 0;
            }
        }
        return total < 0 ? -1 : start;
    }
};

Python

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total = 0
        cur = 0
        start = 0
        
        for i in range(len(gas)):
            netCost = gas[i] - cost[i]
            total += netCost
            cur += netCost
            if cur < 0:
                start = i + 1
                cur = 0
        
        return -1 if total < 0 else start

Java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int cur = 0;
        int start = 0;
        
        for (int i = 0; i < gas.length; i++) {
            int netCost = gas[i] - cost[i];
            total += netCost;
            cur += netCost;
            if (cur < 0) {
                start = i + 1;
                cur = 0;
            }
        }
        return total < 0 ? -1 : start;
    }
}

JavaScript

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    let total = 0;
    let cur = 0;
    let start = 0;
    
    for (let i = 0; i < gas.length; i++) {
        const netCost = gas[i] - cost[i];
        total += netCost;
        cur += netCost;
        if (cur < 0) {
            start = i+1;
            cur = 0;
        }
    }
    return total < 0 ? -1 : start;
};