134. Gas Station
A circular road has n fuel stations. Station i lets you pick up gas[i] units of fuel, and driving from station i to the next station around the circle burns cost[i] units.
You start at a station of your choice with an empty tank, collect that station's fuel, and try to drive the full loop back to where you began, collecting fuel at every station you reach. The tank must never dip below zero between stations.
Your function receives the arrays gas and cost (same length) and returns the 0-based index of the starting station that completes the loop. If several starting stations work, return the smallest such index; if none works, return -1.
Example 1:
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Start at station 3 with 4 units: pay 1 (3 left), pick up 5 (8), pay 2 (6), pick up 1 (7), pay 3 (4), pick up 2 (6), pay 4 (2), pick up 3 (5), pay 5 (0) — home with an empty but never-negative tank. Every earlier start runs dry.
Example 2:
Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Explanation: Total fuel is 9 but the loop costs 10, so no starting point can ever finish.
Constraints:
- 1 ≤ n ≤ 10⁵
- 0 ≤ gas[i], cost[i] ≤ 10⁴
- If several starting stations complete the loop, return the smallest index.
Hints:
First a feasibility fact: if the sum of gas is at least the sum of cost, some start must work — surplus fuel has to pool somewhere on the circle. If the total is short, every start fails. That settles the -1 case with one comparison.
Simulate from a candidate start, tracking the tank as you add gas[i] − cost[i] at each station. The moment it goes negative, that start fails — but notice *which* starts you can rule out along with it.
If you set off from station s and first go negative arriving after station i, then every station in s..i also fails as a start (each would arrive at the same crash point with no more fuel than you had). So jump the candidate straight to i + 1. One pass, and the last surviving candidate is the smallest valid start.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Expected output: 3