Gas Station

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonGoogleMicrosoftMetaApple

Problem Description

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.

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

Constraints

n == gas.length == cost.length
1 ≤ n ≤ 10⁵
0 ≤ gas[i], cost[i] ≤ 10⁴

Net Cost and Deficit Reset Rules

There are two key mathematical properties for this problem:

Total Sum Check: If the sum of all elements in gas is less than the sum of all elements in cost, it is impossible to complete the circuit. In this case, return -1.
Deficit Reset: If we start at index start and cannot reach index i (meaning our tank becomes negative at station i), then no index between start and i (inclusive) can be a valid starting point.
- Why? Because starting at start gives us a non-negative accumulation of gas as we travel. If even with this starting bonus we fail at i, starting later with zero bonus will definitely fail at or before i.
- Therefore, if our running tank value drops below 0, we reset our start index to i + 1 and reset our running tank to 0.

Solution: Single-Pass Greedy

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0;
        for (int g : gas) totalGas += g;
        for (int c : cost) totalCost += c;

        // if overall gas is less than cost, completion is impossible
        if (totalGas < totalCost) return -1;

        int tank = 0;
        int startIdx = 0;

        for (int i = 0; i < gas.length; i++) {
            tank += gas[i] - cost[i];

            // if we run out of gas, reset the starting point to the next station
            if (tank < 0) {
                startIdx = i + 1;
                tank = 0;
            }
        }

        return startIdx;
    }
}

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        # if overall gas is less than cost, completion is impossible
        if sum(gas) < sum(cost):
            return -1

        tank = 0
        start_idx = 0

        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            
            # if we run out of gas, reset starting point
            if tank < 0:
                start_idx = i + 1
                tank = 0

        return start_idx

#include <vector>
#include <numeric>

class Solution {
public:
    int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
        int totalGas = std::accumulate(gas.begin(), gas.end(), 0);
        int totalCost = std::accumulate(cost.begin(), cost.end(), 0);

        if (totalGas < totalCost) return -1;

        int tank = 0;
        int startIdx = 0;

        for (int i = 0; i < (int)gas.size(); i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                startIdx = i + 1;
                tank = 0;
            }
        }

        return startIdx;
    }
};

Complexity Analysis:

Time Complexity: O(N) where N is the number of stations. We scan the array in a single pass.
Space Complexity: O(1) space.