Skip to content

155 — Gas Station

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

155 — Gas Station

LeetCode 134 · Medium. There are n gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station. You begin the journey with an empty tank at one of the gas stations. Given 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 a solution exists, it is guaranteed to be unique.

🍽️ Intuition

Picture driving the loop and tracking your tank's running total as you go: at each station you gain gas[i] and immediately spend cost[i] reaching the next one. If starting from station 0 ever drives the tank negative at some station k, then station 0 can't be a valid start — but neither can any station between 0 and k. Why? Because every one of those stations was reached with a tank total that was 0 or higher at the start (it had to be, or the failure would've happened earlier), meaning starting from any of them only ever gives you a smaller or equal head start compared to carrying whatever surplus accumulated from station 0. So the moment the running tank goes negative, every station up to and including the failure point can be ruled out in one shot, and the next station becomes the new candidate start.

🚩 Pattern-Recognition Cue

"Find the single starting point that lets you complete a circular route without running out" is the running-tank greedy tell: track a candidate start index and a running fuel total in one pass, and whenever the running total goes negative, discard every station tried so far at once (not just the current one) and restart the candidate from the very next station.

🐢 Brute Force

Try every possible starting station, simulating the entire circuit from each one to check if the tank ever goes negative.

func canCompleteCircuitBruteForce(_ gas: [Int], _ cost: [Int]) -> Int {
    let n = gas.count

    for start in 0..<n {
        var tank = 0
        var canComplete = true

        for offset in 0..<n {
            let i = (start + offset) % n
            tank += gas[i] - cost[i]
            if tank < 0 {
                canComplete = false
                break
            }
        }

        if canComplete { return start }
    }

    return -1
}

// smoke test
print(canCompleteCircuitBruteForce([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   // 3
print(canCompleteCircuitBruteForce([2, 3, 4], [3, 4, 3]))               // -1

Big-O: O(n^2) time — every one of the n candidate starting stations simulates the full n-station circuit. O(1) extra space.

🚀 Optimal

Make a single pass tracking the running tank total and the total fuel surplus/deficit across the whole circuit. Whenever the running tank goes negative, every station tried since the current candidate is disqualified at once, so the candidate resets to the very next station.

func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
    var totalTank = 0
    var currentTank = 0
    var start = 0

    for i in 0..<gas.count {
        let diff = gas[i] - cost[i]
        totalTank += diff
        currentTank += diff

        if currentTank < 0 {
            start = i + 1
            currentTank = 0
        }
    }

    return totalTank >= 0 ? start : -1
}

// smoke test — same cases as the brute force
print(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   // 3
print(canCompleteCircuit([2, 3, 4], [3, 4, 3]))               // -1

Big-O: O(n) time — a single left-to-right pass over both arrays. O(1) extra space.

🔑 The Key Insight

The brute force re-simulates the entire circuit from scratch for every candidate start, even though most of that simulation work is identical to a run that already failed. The optimal version leans on the exchange argument sketched above: if the running tank first goes negative at station k while starting from candidate start, no station in [start, k] can possibly be a valid starting point either, because each of them was reached with a running total that was never worse than starting fresh from start — so a fresh start from any of them fails at least as early. That lets the scan discard a whole contiguous block of candidates in one step rather than testing them individually. Separately, totalTank >= 0 is exactly the condition for a solution to exist at all (if the circuit's total gas is less than its total cost, no starting point can possibly work), so checking it once at the end — rather than per-candidate — replaces n full simulations with one.

🔗 Related Chapters

  • Greedy — the running tank total and candidate start are state updated once per station and never revisited, backed by the exchange argument that ruling out a whole block of candidates at once is always safe.
  • Arrays and Strings — both versions scan gas and cost as parallel backing arrays in a single left-to-right (or circular) pass.

🧸 Memory Sentence

Gas Station is one running tank total — the moment it goes negative, every station tried since the last candidate is ruled out at once, and the very next station becomes the new candidate.

✅ Check Your Understanding

  1. Why does the running tank going negative at station k rule out every station between the current candidate and k, not just the current candidate itself?
  2. Why does checking totalTank >= 0 only once, at the very end, correctly decide whether a valid starting station exists at all?
  3. Trace canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) step by step. At which index does currentTank go negative, and what does start become right after?

⬅️ Previous: Jump Game II · Next: Hand of Straights ➡️

Clone this wiki locally