Circular Delivery Route
n depots sit on a circular route, numbered 0 to n - 1. Your van starts with an empty tank. On arriving at depot i (including the depot you start from) you collect fuel[i] litres, and driving from depot i to the next depot (i + 1, or depot 0 after depot n - 1) burns cost[i] litres. You may start at any depot and must drive the full loop back to it, and the tank may never go below 0 litres on the way. Return the smallest index of a depot from which the full loop is possible, or -1 if no depot works.
Example 1
From depot 3: collect 4, drive (tank 3), collect 5 (8), drive (6), collect 1 (7), drive (4), collect 2 (6), drive (2), collect 3 (5), drive home (0). Starting at 0, 1 or 2 runs the tank below 0.
Example 2
The depots give 9 litres in total but the loop burns 10, so no start can work.
Constraints
1 <= len(fuel) == len(cost) <= 1000 <= fuel[i], cost[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.