Gas Station

PracticeNeetCode ↗LeetCode ↗

There are n gas stations arranged in a circle. gas[i] is the fuel available at station i, and cost[i] is the fuel needed to drive from station i to station i + 1. Return the starting station index that lets you complete the full circuit without running out of fuel, or -1 if it's impossible. A solution, if one exists, is unique.

Example

Key Pointers

• If total gas is less than total cost, no starting point can ever work — check that first.
• If a valid start exists, once the running tank goes negative starting from some index, none of the indices between that start and the current position can be a valid start either — you can skip straight past all of them.
• A single left-to-right pass, resetting the candidate start whenever the tank dips negative, replaces the need to test every starting index individually.

Step-by-Step Analysis

1. If sum(gas) < sum(cost), return -1 immediately.
2. Initialize total = 0 (running tank) and start = 0 (candidate answer).
3. For each index i: total += gas[i] - cost[i].
4. If total < 0, set start = i + 1 and reset total = 0.
5. Return start once the loop completes.

Complexity

Time: O(n) — Space: O(1)

Code

def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    if sum(gas) < sum(cost):
        return -1

    total = 0
    start = 0
    for i in range(len(gas)):
        total += gas[i] - cost[i]
        if total < 0:
            start = i + 1
            total = 0

    return start

Code Explanation

How the solution above works, piece by piece.

1. If total gas is less than total cost, no start works → −1. Otherwise exactly one start works (the problem guarantees uniqueness).
2. Drive from start, adding gas[i] − cost[i] to the tank.
3. If the tank goes negative at i, no station from start to i can be the answer: each of them would arrive at i with even less fuel. So jump start to i + 1 and reset.
4. Whatever start survives to the end is the answer; the total check guarantees the wrap-around part works.
5. One pass, O(1) space.

Visual Walkthrough

Running it on gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]:

Video Explanation

NeetCode — Greedy, LeetCode 134