Write can_complete_circuit(gas: list[int], cost: list[int]) -> int.
n fuel stations sit on a circular road. Stopping at station i adds gas[i] to your tank, and driving from station i to station (i + 1) % n burns cost[i]. The tank has no limit and starts empty. Return the index of a station you can start from and drive all the way around back to it without the tank going below zero, or -1 if no such station exists. If several starts work, any of them is accepted.
Example: gas = [3, 1, 4], cost = [2, 3, 1] gives 2. From station 2: tank 4 − 1 = 3, then 3 + 3 − 2 = 4, then 4 + 1 − 3 = 2.
gas = [1, 1], cost = [2, 1] gives -1 (total gas is less than total cost).
Constraints: 1 <= n <= 10^5, 0 <= gas[i], cost[i] <= 10^4.
Trying each start and simulating is O(n²) and fails the large test; aim for O(n).
Show hint
compare total gas with total cost first. Then, if you start somewhere and the tank goes negative at station i, what does that tell you about every start between there and i?