Pick The Depot To Complete The Loop
A delivery van runs a circular route of n stops. At stop i it can pick up gas[i] litres, and travelling to the next stop costs cost[i] litres. Find the unique starting stop from which the van can complete the full loop, or report that none exists.
Problem
Given two integer arrays gas and cost of length n, return the starting index from which you can travel around the circuit once in the forward direction, refuelling at each stop. If no such start exists, return -1. A valid solution is guaranteed unique when it exists.
Input
Two integer arrays gas[] and cost[] of equal length n.
Output
The starting index (0-based), or -1 if the loop cannot be completed.
Constraints
- 1 ≤ n ≤ 1e5
- 0 ≤ gas[i], cost[i] ≤ 1e4
Examples
Example 1
Input
gas=[1,2,3,4,5] cost=[3,4,5,1,2]
Output
3
Starting at index 3 the running tank never goes negative around the loop.
Example 2
Input
gas=[2,3,4] cost=[3,4,3]
Output
-1
Total gas 9 < total cost 10, so no start can complete the circuit.