Find a starting gas station index from which a circular route can be completed, or return -1 if impossible.
You are given two integer arrays gas and cost, each of length n. Station i provides gas[i] units of fuel, and it takes cost[i] units of fuel to travel from station i to station (i + 1) % n.
You begin with an empty tank and may choose any station as the starting point. If you can travel around the entire circuit once without the fuel in your tank ever dropping below zero, return the index of one valid starting station. If no such station exists, return -1.
If a valid starting station exists, it is guaranteed to be unique in the standard problem formulation.
Input Format
- Two integer arrays
gasandcost gas[i]andcost[i]correspond to stationi- The route is circular, so after station
n - 1you travel back to station0
Output Format
- Return a single integer
- The integer is the starting station index, or
-1if the full circuit cannot be completed
Constraints
1 <= n <= $10^{5}$0 <= gas[i], cost[i] <= $10^{4}$- The answer, if it exists, is unique in the standard formulation
Example 1
Input
gas = [1,2,3,4,5] cost = [3,4,5,1,2]
Output
3
Explanation
Starting at station 3 gives enough fuel to complete the circuit: tank changes are +3, +3, -1, -2, -1, never dropping below 0.
Example 2
Input
gas = [2,3,4] cost = [3,4,3]
Output
-1
Explanation
The total gas is less than the total cost, so no starting station can complete the circuit.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.