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).

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 exactly one valid start (greedy can find it).

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

• Invariant: when scanning, tank represents the net gas since the last candidate start.
• The algorithm maintains a feasible best-so-far state while scanning.
• Each greedy update preserves feasibility and never discards a possible optimal answer.
• When the scan ends, the recorded state represents the optimal solution.

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).

Complexity

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

Implementation notes (Go)

• Use 64-bit if you are concerned about large sums.