Gas Station

Problem

There are n gas stations arranged in a circle. Station i has gas[i] units of fuel, and it costs cost[i] units to drive from station i to the next station i+1 (wrapping from n-1 back to 0).

You start with an empty tank at some station and drive clockwise around the entire loop, filling up at each station before leaving. Return the index of the starting station from which you can complete the full circuit exactly once, or -1 if no such start exists. When a valid start exists, it is guaranteed to be unique.

Examples

• gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3 — starting at station 3: tank goes 4-1=3, then 3+5-2=6, then 6+1-3=4, 4+2-4=2, 2+3-5=0 ≥ 0 the whole way.
• gas = [2,3,4], cost = [3,4,3] → -1 — total gas 9 < total cost 10, so the loop is impossible from anywhere.
• gas = [5,1,2,3,4], cost = [4,4,1,5,1] → 4 — starting at station 4 keeps the tank non-negative around the circle.

Constraints

• n == len(gas) == len(cost), 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

The 10^5 bound rules out the O(n^2) “try every start” simulation; an O(n) single pass is expected.

Think about it first

TL;DR

If total gas ≥ total cost a start exists; find it in one pass by resetting the candidate whenever the running tank goes negative — O(n) time, O(1) space.

Approach 1 — Brute force: try every starting station

For each candidate start, simulate the whole circle and check the tank never goes negative.

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for start in range(n):
            tank = 0
            ok = True
            for step in range(n):
                i = (start + step) % n
                tank += gas[i] - cost[i]
                if tank < 0:
                    ok = False
                    break
            if ok:
                return start
        return -1

Complexity: O(n^2) time, O(1) space. Each of n starts triggers a full O(n) simulation. At n = 10^5 that is 10^10 operations — far too slow.

Approach 2 — One-pass greedy

Two facts unlock the linear solution.

Feasibility: Define diff[i] = gas[i] - cost[i]. A full loop is possible iff sum(diff) >= 0, i.e. total gas ≥ total cost. If the totals fall short, no start can work, so return -1 immediately.

The greedy-choice property (why skipping ahead is safe): Suppose you start at candidate s and the running tank first goes negative at station i (that is, diff[s] + diff[s+1] + ... + diff[i] < 0, and every shorter prefix from s was non-negative). Then no station in [s, i] can be a valid start. Why? For any k with s < k <= i, the partial sum from s to k-1 was >= 0 (that is exactly why the tank had not yet failed before reaching k). So the run starting at k reaches i with sum = (sum from s to i) - (sum from s to k-1) <= sum from s to i < 0 — it fails no later than i too. Every intermediate start inherits the failure, so we may leap the candidate straight to i+1 and never look back. Because we discard whole doomed prefixes, one left-to-right sweep suffices.

Given the totals are non-negative, whatever candidate survives to the end of the sweep must complete the loop — a slick consequence: the deficits before the final start are exactly cancelled by the surplus after it.

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        start = 0
        tank = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:        # candidate [start..i] is doomed
                start = i + 1   # leap past the whole failed prefix
                tank = 0
        return start

Walkthrough on gas = [1,2,3,4,5], cost = [3,4,5,1,2] → diff = [-2,-2,-2,3,3]:

1. sum(gas)=15 >= sum(cost)=15, so a start exists.
2. i=0: tank = -2 < 0 → start=1, tank=0.
3. i=1: tank = -2 < 0 → start=2, tank=0.
4. i=2: tank = -2 < 0 → start=3, tank=0.
5. i=3: tank = 3, stays ≥ 0.
6. i=4: tank = 3+3 = 6, stays ≥ 0.
7. Sweep ends → start = 3. ✅ (matches the expected answer.)

Complexity: O(n) time (the sum calls plus one sweep), O(1) extra space.

Common pitfalls

• Skipping the total-fuel feasibility check. The one-pass loop returns a start index unconditionally; without confirming sum(gas) >= sum(cost) you may return a station that cannot actually finish.
• Resetting start to i instead of i + 1 — station i is the one where you ran dry, so it cannot be the fresh start.
• Forgetting to reset tank to 0 when you move the candidate; carrying the negative balance forward corrupts the next segment.

Pattern takeaway

When a running accumulator crosses a failure threshold, you can often discard the entire prefix that led there in one jump rather than retrying each earlier start. Pair a cheap global feasibility test (totals) with a single greedy sweep that abandons doomed prefixes.