There are n gas stations arranged in a circle. You are given two arrays gas and cost. At station i you collect gas[i] units of gas; it costs cost[i] to travel to station i+1. Starting with an empty tank, return the starting station index if you can complete the circuit once, otherwise return -1.
gas = [1,2,3,4,5] cost = [3,4,5,1,2]3gas = [2,3,4] cost = [3,4,3]-1diff[i] = gas[i] - cost[i] (net gas at station i)total += diff — tracks global feasibility across all stationstank += diff — tracks journey from current starttank < 0: start = i + 1; tank = 0 — reset candidatetotal ≥ 0 ? start : -1 — feasible only if net gas non-negativeTwo key observations: (1) If total ≥ 0, a valid start must exist — total gas is sufficient. (2) Whenever the running tank drops below zero after station i, none of the stations from the current start to i can be the answer (they'd all result in a negative tank sooner). So we safely skip to i+1. The last valid start candidate after the full scan is the answer.