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.
Simulating a trip from every station is O(n²). Two facts make it linear.
First, if the total gas is less than the total cost, no start can work. Second, if the tank goes negative at station i, no station between the start and i can work either. So reset the start to i plus 1 and empty the tank.
A failure at i rules out every start before it. If the total is not negative, the last reset is the answer.
Run the animation above on your own input, or watch the 1:25 video explanation of Gas Station with a dry run and Java code.