Gas Station

mediumGreedy & Intervals35 stepsJava · Python · C++

Find the station from which you can drive the whole circle. If total gas ≥ total cost, a solution exists. Drive from station 0 keeping the tank; whenever the tank goes negative, no station from the current start up to here works, so start fresh at the next station.

▶ Watch the animated trace

Traced input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] → 3. Original problem: neetcode.io/problems/gas-station

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

One pass.

Key idea

If the total gas is less than the total cost, it's impossible from anywhere.
If you run dry at station i starting from s, every start between s and i also runs dry by i.
So jump the start to i + 1 and reset the tank.

Common mistakes

Trying every start is O(n²).
Forgetting the total check: the last start candidate isn't guaranteed without it.

Solution

Java

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int gain = gas[i] - cost[i];
        total += gain;
        tank += gain;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

Python

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

C++

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        int gain = gas[i] - cost[i];
        total += gain;
        tank += gain;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Impossible Total gas 9 < total cost 10.	`gas = [2, 3, 4], cost = [3, 4, 3]`	`-1`
Single station Enough to loop back.	`gas = [5], cost = [4]`	`0`
Exactly enough The tank hits 0 but never goes negative.	`gas = [1, 1], cost = [1, 1]`	`0`