134. Gas Station (Medium)

Problem

You have n gas stations arranged in a circle. Station i provides gas[i] units. Traveling from station i to the next station consumes cost[i] units. You start with an empty tank at one station.

Return the starting index that lets you complete one clockwise circuit. Return -1 when no start works. If a solution exists, the input guarantees that it is unique.

Examples

• gas = [1,2,3,4,5], cost = [3,4,5,1,2] returns 3. Starting at station 3 produces running tank values 3, 6, 4, 2, 0 after each drive.
• gas = [2,3,4], cost = [3,4,3] returns -1. The route provides 9 units but requires 10.

Constraints

• $n = \text{gas.length} = \text{cost.length}$
• $1 \leq n \leq 10^5$
• $0 \leq \text{gas}[i], \text{cost}[i] \leq 10^4$
• A valid starting index is unique when it exists.

LeetCode 134, Gas Station in Top Interview 150, Medium.

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try every start

For each starting index, simulate at most n drives. Stop as soon as the tank becomes negative. This follows the definition directly, but much of the same route can be scanned again for later candidates.

Python

def can_complete_circuit(gas, cost):
    n = len(gas)                                # L1: O(1)
    for start in range(n):                      # L2: outer loop, n starts
        tank = 0
        for i in range(n):                      # L3: inner loop, n steps per start
            idx = (start + i) % n               # L4: O(1)
            tank += gas[idx] - cost[idx]        # L5: O(1)
            if tank < 0:
                break
        else:
            return start
    return -1

TypeScript

function canCompleteCircuit(gas: number[], cost: number[]): number {
    const n = gas.length;                                   // L1: O(1)
    for (let start = 0; start < n; start++) {              // L2: outer loop, n starts
        let tank = 0;
        let ok = true;
        for (let i = 0; i < n; i++) {                      // L3: inner loop, n steps per start
            const idx = (start + i) % n;                   // L4: O(1)
            tank += gas[idx] - cost[idx];                  // L5: O(1)
            if (tank < 0) { ok = false; break; }
        }
        if (ok) return start;
    }
    return -1;
}

Go

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)                                           // L1: O(1)
    for start := 0; start < n; start++ {                   // L2: outer loop, n starts
        tank := 0
        ok := true
        for i := 0; i < n; i++ {                           // L3: inner loop, n steps per start
            idx := (start + i) % n                         // L4: O(1)
            tank += gas[idx] - cost[idx]                   // L5: O(1)
            if tank < 0 { ok = false; break }
        }
        if ok { return start }
    }
    return -1
}

Swift

final class Solution {
    func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
        for start in gas.indices {
            var tank = 0, valid = true
            for step in gas.indices {
                let station = (start + step) % gas.count
                tank += gas[station] - cost[station]
                if tank < 0 { valid = false; break }
            }
            if valid { return start }
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = len(gas) = len(cost).

Line	Per-call cost	Times executed	Contribution
L2 (outer loop)	$O(1)$	n	$O(n)$
L3-L5 (inner simulation)	$O(1)$	up to n per start	$O(n^2)$, dominant

For each candidate start, we simulate up to n steps. In the worst case, nearly every candidate travels nearly the entire route before failing.

Complexity

• Time: $O(n^2)$, driven by a full simulation for each candidate start.
• Space: $O(1)$.

Approach 2: Greedy single pass (canonical)

Replace each station with its net contribution:

$\text{net}[i] = \text{gas}[i] - \text{cost}[i]$

The solution follows from two facts:

1. If the sum of all net contributions is negative, no start can create missing gas.
2. If a candidate start reaches station i with a negative tank, every station from that candidate through i is also impossible. The next candidate can jump directly to i + 1.

Python

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):                # L1: O(n) feasibility check
        return -1
    tank = 0                                # L2: O(1)
    start = 0                               # L3: O(1)
    for i in range(len(gas)):               # L4: single pass, n iterations
        tank += gas[i] - cost[i]            # L5: O(1)
        if tank < 0:                        # L6: O(1)
            start = i + 1
            tank = 0
    return start

TypeScript

function canCompleteCircuit(gas: number[], cost: number[]): number {
    const totalGas = gas.reduce((a, b) => a + b, 0);
    const totalCost = cost.reduce((a, b) => a + b, 0);
    if (totalGas < totalCost) return -1;                   // L1: O(n) feasibility check
    let tank = 0;                                          // L2: O(1)
    let start = 0;                                         // L3: O(1)
    for (let i = 0; i < gas.length; i++) {                 // L4: single pass, n iterations
        tank += gas[i] - cost[i];                          // L5: O(1)
        if (tank < 0) {                                    // L6: O(1)
            start = i + 1;
            tank = 0;
        }
    }
    return start;
}

Go

func canCompleteCircuit(gas []int, cost []int) int {
    totalGas, totalCost := 0, 0
    for _, g := range gas { totalGas += g }
    for _, c := range cost { totalCost += c }
    if totalGas < totalCost { return -1 }                  // L1: O(n) feasibility check
    tank := 0                                              // L2: O(1)
    start := 0                                             // L3: O(1)
    for i := range gas {                                   // L4: single pass, n iterations
        tank += gas[i] - cost[i]                           // L5: O(1)
        if tank < 0 {                                      // L6: O(1)
            start = i + 1
            tank = 0
        }
    }
    return start
}

Swift

final class Solution {
    func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
        var total = 0, tank = 0, start = 0
        for index in gas.indices {
            let balance = gas[index] - cost[index]
            total += balance; tank += balance
            if tank < 0 { start = index + 1; tank = 0 }
        }
        return total >= 0 ? start : -1
    }
}

Where the time goes, line by line

Variables: n = len(gas) = len(cost).

Line	Per-call cost	Times executed	Contribution
L1 (sum check)	$O(n)$	1	$O(n)$
L4-L6 (single pass)	$O(1)$	n	$O(n)$, dominant

The sum check and greedy scan are each linear. Their costs add to $O(n)$.

Complexity

• Time: $O(n)$.
• Space: $O(1)$.

Why failed candidates can be skipped

Suppose a candidate start reaches station i with a negative tank. The candidate survived every earlier drive, so the balance from start to any intermediate station k - 1 was non-negative. Removing that non-negative prefix from the negative balance through i leaves a negative balance from k through i.

That means every k in [start, i] also fails by station i. None of those positions needs its own simulation. Reset the tank and continue with i + 1.

Why the final candidate completes the circle

The local tank answers whether the current candidate has failed. The total balance answers whether the route is feasible at all. If total gas covers total cost, all discarded prefixes can be paid for by the surplus accumulated from the final candidate through the end of the array. The final candidate therefore survives the wraparound portion too.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

How to recognize this pattern

The signal: The problem asks for a starting point on a circular sequence, and each position has a local gain and local cost. Converting those two arrays into gas[i] - cost[i] exposes a running-balance problem.

The tempting wrong move: Starting at the station with the most gas ignores the cost of leaving that station and the deficits ahead. In the first example, station 4 has the most gas, but station 3 is the answer.

The elimination clue: A failed running balance often proves that a whole prefix of candidates is impossible. When one failure rules out a contiguous range, look for a greedy jump instead of restarting a simulation from each position.

The mental model: Global balance proves that some solution exists. Local balance finds where that solution begins.

Approach comparison

Approach	Time	Space
Try every start	$O(n^2)$	$O(1)$
Greedy single pass	$O(n)$	$O(1)$

Key takeaways

• Convert each station into one net value, gas[i] - cost[i].
• Keep global feasibility separate from the local candidate balance.
• A negative local balance eliminates every candidate since the last reset.
• The circle does not require a second simulation once total balance is non-negative.

References

• LeetCode 134: Gas Station
• LeetCode Gas Station editorial

Related topics

• Greedy problems
• 55. Jump Game
• 45. Jump Game II
• Arrays

Related concepts

• Greedy algorithms, failed prefixes can be discarded without revisiting them.
• Greedy exchange arguments, the elimination proof explains why the next candidate loses nothing.
• Array scans, one pass maintains both total and local balances.