Gas Station

MediumGreedyNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

There are n gas stations on a circular route. gas[i] is the fuel you pick up at station i, and cost[i] is the fuel needed to drive from station i to station i + 1, with the last station leading back to station 0. You start with an empty tank at a station of your choice. Return the index of the station from which you can drive the full loop once without running out, or -1 if none works. If an answer exists, it is unique.

Examples

gas = [1,2,3,4,5], cost = [3,4,5,1,2] returns 3

Start at station 3: take 4 and spend 1 (tank 3), then +5 -2 (6), +1 -3 (4), +2 -4 (2) and +3 -5 (0), arriving back at station 3 without ever going negative. Every other start runs dry before finishing.

gas = [2,3,4], cost = [3,4,3] returns -1

The stations hold 9 fuel in total but the full loop costs 10, so no starting point can complete it.

Constraints

n == gas.length == cost.length
1 <= n <= 10^5

Hints

Hint 1

If you can't reach the next station from some starting point, what does that say about every station in between?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

If total gas minus total cost is negative, no start works. Otherwise scan once, keeping a tank balance from the current candidate start. When the tank goes negative at station i, no station between start and i can work either, since each of them reaches i with no more fuel than start had there. So move start to i + 1 and reset the tank to 0. With a non-negative total, the start left standing completes the loop.

Time

O(n)

Space

O(1)

Pitfall

Simulating the loop from every station is O(n^2) and times out. And don't skip the total check: for gas = [2,3,4], cost = [3,4,3] the reset logic alone ends on start 2, but the answer is -1.

Solutions

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

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