Gas Station

You have n gas stations arranged in a circle. At station i, you can take gas[i] units of gas, and it costs cost[i] units to travel to station i+1 (wrapping around).

Return the starting station index if you can complete the circuit once, otherwise return -1.

A brute-force start check is O(n^2). A greedy scan can solve it in O(n).

Why this is worth learning

Total balance decides existence, while a failed candidate lets you discard an entire block of starts. Feasibility does not imply uniqueness; several starts can work.

Before coding: one-minute experiment

For gas=[2,2] and cost=[1,1], how many valid starts are there, and which does the supplied scan return?

Function signature

func CanCompleteCircuit(gas []int, cost []int) int

Inputs / outputs

• gas[i]: gas available at station i.
• cost[i]: gas required to move from station i to i+1.
• Return: starting index (0-based) or -1.

Example

gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3

Start at 3: 4->5->1->2->3 works.

Constraints

• 1 <= len(gas) == len(cost) <= 100_000
• 0 <= gas[i], cost[i] <= 1_000_000_000

Core idea (near-solution)

Two facts:

1. If total gas < total cost, no solution exists.
2. If total gas >= total cost, there is at least one valid start. Uniqueness does not follow from the total check: gas=[1,1], cost=[1,1] permits both starts. The reference preserves its deterministic first surviving candidate.

Greedy scan:

• Track tank = current gas in the tank.
• If tank drops below 0 at station i, then no station from the current start up to i can be a valid start. Reset the start to i+1 and clear the tank.

Invariant: when scanning, tank represents the net gas since the last candidate start.

Algorithm (step-by-step)

1. Compute totalGas and totalCost. If totalGas < totalCost, return -1.
2. Initialize start = 0, tank = 0.
3. For each station i from 0 to n-1:
   • tank += gas[i] - cost[i].
   • If tank < 0, set start = i+1 and reset tank = 0.
4. Return start.

Correctness sketch

Let d[i]=gas[i]-cost[i]. Suppose a candidate s first becomes negative at i. Every earlier prefix from s to j-1, for s<=j<=i, was nonnegative. Hence sum(d[j:i+1])=sum(d[s:i+1])-sum(d[s:j]) is negative too, so every start in [s,i] fails before or at i. Resetting to i+1 discards no feasible start. Equivalently, the final candidate lies immediately after a strict minimum of the prefix sums. If the total sum is nonnegative, all suffix and wrapped-prefix balances from that minimum are nonnegative, proving this candidate completes the circuit. A negative total makes every start impossible.

Trace (hand walkthrough)

Example input:
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3

Start at 3: 4->5->1->2->3 works.

Walk:
- diffs = gas-cost = [-2,-2,-2,3,3], total=0 so possible
- i=0 tank=-2 -> reset start=1, tank=0
- i=1 tank=-2 -> reset start=2, tank=0
- i=2 tank=-2 -> reset start=3, tank=0
- i=3 tank=3; i=4 tank=6 -> end with start=3

Pitfalls to avoid

• Forgetting the total gas check before the greedy scan.
• Resetting start too late (must reset immediately when tank < 0).

Debugging lens

Test a reset near the end, a zero total, and multiple feasible starts. Do not reset when tank equals zero: the current candidate remains feasible.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• The full domain requires the course's 64-bit Go target: totals can reach 100_000 × 1_000_000_000 = 10^14. An int32 accumulator would overflow even if the returned station index is small.

Reconstruction checkpoint

For gas=[2,2] and cost=[1,1], how many valid starts are there, and which does the supplied scan return?

Return to Array & String · Module quiz