Gas Station

There are n gas stations in a circle. Station i gives you gas[i] units of fuel, and driving from station i to station i + 1 (wrapping around at the end) costs cost[i] units. Return the index of the station where you can start with an empty tank and complete the whole circuit exactly once. If it is impossible, return -1.

The canonical interview version guarantees that if a solution exists, it is unique.

Input / output

• Input: gas: int[], cost: int[]
• Output: starting index, or -1 if no full circuit is possible

Examples

1. gas = [1,2,3,4,5], cost = [3,4,5,1,2] returns 3.
2. gas = [2,3,4], cost = [3,4,3] returns -1.
3. gas = [5], cost = [4] returns 0.

Constraints

• 1 <= gas.length == cost.length <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

Target complexity

• Aim for O(n) time and O(1) extra space.

Hints

1. First ask whether the total gas is at least the total cost.
2. If your running tank becomes negative between start and i, none of the stations between them can be the answer.

Follow-up Why does the proof of correctness depend on resetting the candidate start only when the running tank becomes negative?