Gas Station

Problem

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, 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

Examples

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. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Solution

Understanding the Problem

Lets try to understand the problem. gas array tells us gas at ith station, and cost array tells us cost of reaching next station, or amount of fuel we will burn to reach next station. So to sum up:

• Each index in the gas array represents the amount of gas available to fill up your car with.
• Each index in the cost array represents the amount of gas that will be used when travelling from this gas station to next.

So, lets take eg. 1. We have array:

index: 0 1 2 3 4
gas:   1 2 3 4 5
cost:  3 4 5 1 2

Lets calculate diff array:

index: 0   1   2  3  4
gas:   1   2   3  4  5
cost:  3   4   5  1  2
diff:  -2 -2  -2  3  3

So, we cannot start at index 0, 1 and 2 as cost is higher than the fuel. But if we have infinte fuel tank. So, we start at index 3, we can save 3 litres of gas and move to index 4. There also we save 3 liters. Then we use this total 6 litres on circular array's indices - 0, 1 and 2. So, sum(gas) >= sum(cost) arrays.

Method 1 - Naive Solution

An intuitive solution involves testing each petrol station as the starting point and checking whether completing the circuit is possible. If a valid starting station is found, it is returned as the result.

The naive approach involves simulating the journey starting from each gas station:

1. For each station, calculate the net fuel balance while traversing the circuit.
2. If the fuel balance becomes negative during the traversal, terminate the journey prematurely and move to the next starting point.
3. If the vehicle successfully completes the circuit, check if the fuel balance meets the criteria (>= 0) and return the start index.

Code

Java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {  // Iterate over each station as a possible starting point
            int totalFuel = 0;
            int stopCount = 0, j = i;
            while (stopCount < n) {  // Check if the circuit can be completed
                totalFuel += gas[j % n] - cost[j % n];
                if (totalFuel < 0) break;  // Stop if fuel is insufficient
                stopCount++;
                j++;
            }
            if (stopCount == n && totalFuel >= 0) return i;  // Ensure the entire circuit is covered
        }
        return -1;  // Return -1 if no valid starting station is found
    }
}

Python

class Solution:
    def canCompleteCircuit(self, gas, cost):
        n = len(gas)
        for i in range(n):  # Iterate over every station as starting point
            total_fuel = 0
            stop_count = 0
            j = i
            while stop_count < n:  # Loop to check feasibility of completing circuit
                total_fuel += gas[j % n] - cost[j % n]
                if total_fuel < 0:  # Break if fuel runs out
                    break
                stop_count += 1
                j += 1
            if stop_count == n and total_fuel >= 0:  # Ensure all stations are visited
                return i
        return -1  # Return -1 if no valid starting station is found

Complexity

• ⏰ Time complexity: O(n^2), because for each starting station O(n), it simulates a journey along the entire circuit O(n).
• 🧺 Space complexity: O(1)

Method 2 - Track Total Surplus and Current Surplus

The brute-force ran a simulation, such that, as soon as a gas balance became negative, it moved the car to the next station as a starting point. But this is inefficient and inorder for us to understand why? we have to look at what makes car stop.

Look at the array:

index: 0   1   2  3  4
gas:   1   2   3  4  5
cost:  3   4   5  1  2
diff:  -2 -2  -2  3  3

The first three stations (indices 0, 1, and 2) are invalid starting points, as they cannot sustain the journey even temporarily. This means fuel accumulation compared to consumption results in a surplus or, at the very least, breaks even before the failure. If the fuel deficit occurred anywhere earlier, the car would have stopped before reaching those stations.

Thus, if we fail to begin at the first station, indices 1, 2, and 3 are also not viable starting points. To succeed, the condition sum(gas) >= sum(cost) must hold, which is tracked using totalSurplus. A secondary variable, surplus, keeps track of the local fuel balance and helps identify the viable starting index.

Approach

• Iterate through the stations and calculate the net gas balance (gas[i] - cost[i]).
• Maintain two variables:
  • totalSurplus: Tracks the overall fuel surplus across all stations to determine feasibility (sum(gas) >= sum(cost)).
  • surplus: Tracks the local fuel balance during traversal to reset the starting index when the balance turns negative.
• If totalSurplus is negative at the end of the iteration, return -1, as no valid starting station exists. Otherwise, return the identified starting index.

Code

Java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int totalSurplus = 0;  // Tracks overall surplus
        int surplus = 0;  // Tracks local surplus
        int start = 0;  // Potential starting index

        for (int i = 0; i < n; i++) {
            totalSurplus += gas[i] - cost[i];
            surplus += gas[i] - cost[i];
            if (surplus < 0) {  // Reset surplus and move start index
                surplus = 0;
                start = i + 1;
            }
        }
        return (totalSurplus < 0) ? -1 : start;  // Return starting index if valid
    }
}

Python

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        n = len(gas)
        total_surplus = 0  # Tracks overall surplus
        surplus = 0  # Tracks local surplus
        start = 0  # Potential starting index

        for i in range(n):
            total_surplus += gas[i] - cost[i]
            surplus += gas[i] - cost[i]
            if surplus < 0:  # Reset surplus and update starting index
                surplus = 0
                start = i + 1

        return -1 if total_surplus < 0 else start  # Return start if valid, else -1

Rust

pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
	let mut total_surplus = 0;
	let mut surplus = 0;
	let mut start: i32 = 0;
	for i in 0..gas.len() {
		let cur_surplus = (gas[i] - cost[i]);
		total_surplus += cur_surplus;
		surplus += cur_surplus;
		if surplus < 0 {
			surplus = 0;
			start = i as i32 + 1;
		}
	}
	return if total_surplus < 0 { -1 } else { start };
}

Complexity

• ⏰ Time complexity: O(n), as it performs a single pass through the arrays while calculating fuel balances.
• No nested iterations, unlike the brute-force approach.
• 🧺 Space complexity: O(1)