Gas Station

Problem

There are n gas stations arranged in a circle. gas[i] is the fuel available at station i, and cost[i] is the fuel needed to drive from station i to station i+1 (wrapping around from n-1 back to 0). You start with an empty tank at some station and drive clockwise, picking up gas[i] and spending cost[i] at each leg. Return the index of the station you should start from to complete the full circle once, or -1 if it's impossible. The answer, when it exists, is guaranteed unique.

Examples

Trace the first on paper — start at station 3:

tank 0+4−1=3 at 3, then 3+5−2=6 at 4, 6+1−3=4 at 0, 4+2−4=2 at 1, 2+3−5=0 at 2. Full loop.

Constraints

1 ≤ n ≤ 10⁵ · 0 ≤ gas[i], cost[i].

Attempt it first

The obvious solution — try each of the n stations as a start and simulate the loop — is O(n²) and correct. Write that first if you need to; it clarifies the mechanics. Then look for the two structural facts that let you find the answer in a single pass. Both are provable, and the second one is the real prize.