Gas Station

Problem n gas stations form a circle: station i provides gas[i]; driving to the next costs cost[i]. Starting with an empty tank, return the unique starting index allowing one full clockwise circuit, or -1.

Input / Output

• Input: int arrays gas, cost. Output: starting index or -1.

Constraints

• n up to 10^5; O(n) greedy expected; trying every start is O(n^2).

Example

• gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3.

Expected approach

• One pass, two accumulators: total surplus Σ(gas−cost) decides feasibility (< 0 → -1); a running tank resets the candidate start to i+1 whenever it drops below zero (no station in the failed stretch can be a valid start — prove that claim). O(n)/O(1). The two lemmas (global surplus ⇒ some start works; failure discards the whole prefix) are the interview substance.