Where to Start a Circular Route

MediumArraysGreedy303 tests

There are n stops on a circular road, numbered 0 to n - 1. After stop n - 1 the road goes back to stop 0.

You get two arrays of the same length:

fuel[i] is the amount of fuel you can take at stop i.
cost[i] is the amount of fuel needed to drive from stop i to the next stop.

You choose one stop to start from, with an empty tank. At each stop you take all of its fuel, then drive to the next stop. The tank has no size limit. The tank may reach exactly 0, but it must never need more fuel than it holds.

You complete the route when you drive all the way around and arrive back at the starting stop.

Return the smallest starting index from which you can complete the route. If no start works, return -1.

Note

More than one start can work. Return the smallest one.

If the total fuel is less than the total cost, no start works. Otherwise, walk once from left to right with a running tank. When the tank goes below zero at stop i, no start up to i can work, so try i + 1 next.

Examples

Example 1

Input:: [2,5,1,4], [3,2,4,1]
Output:: 1

From stop 0 the tank is 2 but the drive needs 3, so it fails. From stop 1 the tank after each drive is 3, 0, 3, 2, so it works. Stop 3 also works, but 1 is smaller.

Example 2

Input:: [3,1], [2,3]
Output:: -1

The total fuel is 4 and the total cost is 5, so no start can finish.

Example 3

Input:: [6], [6]
Output:: 0

There is one stop. You take 6 fuel and the drive back to the same stop needs 6, so the tank ends at exactly 0.

Constraints

1 <= n <= 12
fuel.length == cost.length == n
0 <= fuel[i], cost[i] <= 10

Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.