Gas Station Problem

Problem N gas stations sit on a circular route. Station i holds gas[i] units of fuel, and driving from station i to station i+1 burns cost[i]. Starting with an empty tank, find the index of a station you can begin at and complete the full circuit, or return -1 if no such station exists.

Input / Output

• Input: two arrays gas and cost, each of length N.
• Output: the starting station index, or -1 if the circuit cannot be completed from anywhere.

Constraints

• If a valid start exists, it is guaranteed to be unique.
• The route wraps: after station N-1 you return to station 0. The tank is unlimited but must never go negative part-way through a leg.
• Target O(n) time and O(1) space — beat the O(n^2) "simulate from every start".

Example

• gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3.
• gas = [2,3,4], cost = [3,4,3] → -1 (total gas 9 < total cost 10).