Gas Station

Problem

There are n gas stations arranged in a circle. Station i offers gas[i] units of fuel, and driving from station i to station i + 1 (wrapping around from the last station to the first) consumes cost[i] units. You begin with an empty tank at a station of your choosing and must complete one full lap, visiting every station once in order. Return the index of a station from which the lap can be completed, or -1 if no such station exists. If several stations would work, any one of them is accepted.

• Between 1 and 200,000 stations.
• Every gas[i] and cost[i] is a non-negative integer no larger than 100,000.

Examples

• gas = [2, 1, 8, 9, 8], cost = [4, 8, 5, 3, 7] → 2. The per-station surplus is [-2, -7, 3, 6, 1]. Leaving station 2 the tank reads 3, 9, 10, 8, 1 after each leg and never goes negative; leaving station 0 or 1 you are short on the very first leg, and leaving 3 or 4 you run dry on the way to station 2.
• gas = [4, 2, 7], cost = [5, 3, 6] → -1. Total gas 13 is less than total cost 14, so no start can work.
• gas = [6], cost = [6] → 0. One station; you just need gas[0] >= cost[0].

Hints

1. If the total gas is less than the total cost, is any start possible? And if it is not less?
2. Suppose you start at s and run dry just before reaching station f. Could any station strictly between s and f be a valid start?
3. One pass: track the running tank; whenever it goes negative, reset the tank and move the candidate start to the next station. The final candidate is the answer if the global total is non-negative.