552. Fuel Loop
A delivery van drives around a circular ring road with n fuel stops, numbered 0 to n - 1 in driving order. At stop i the van collects exactly gas[i] units of fuel, and driving from stop i to the next stop (stop 0 follows stop n - 1) burns cost[i] units. The tank is unlimited and starts empty, and the van always collects the fuel at a stop before leaving it.
Return the smallest starting stop from which the van can complete one full lap and return to where it began without the tank ever going below zero (arriving with exactly zero is fine). If no starting stop works, return -1.
Aim for one pass, O(n) time and O(1) space. Trying every start with a full simulation is O(n^2) and too slow.
Example 1
- Input:
- gas = [4,1,3,2,6], cost = [3,4,2,5,1]
- Output:
- 4
- Explanation:
Starting at stop 4 the tank holds 5, 6, 3, 4 and 1 after stops 4, 0, 1, 2 and 3, never negative, so the lap completes; no earlier stop works.
Example 2
- Input:
- gas = [3,3], cost = [3,3]
- Output:
- 0
- Explanation:
Fuel exactly matches the cost at every stop, so starting at stop 0 works and 0 is the smallest index.
Example 3
- Input:
- gas = [1,2,3], cost = [3,3,3]
- Output:
- -1
- Explanation:
Total fuel is 6 but total cost is 9, so no starting stop can finish a lap.
Constraints
1 ≤ n ≤ 1000000, andgas.length == cost.length == n0 ≤ gas[i], cost[i] ≤ 1000000000- Running totals can exceed 32 bits, so use 64-bit sums.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)