[Java] Find index in circular array so that rolling sum never falls below zero

The title is actually a simplification of the following problem:

given a car with unlimited fuel capacity, an array indicating the amount of fuel that can be put in the car at a specific city i and another array indicating the amount of fuel necessary to travel from city i to the next, return the index of any city that allows making a round trip passing through all other cities in the order they appear.

Example:

gasAtCity = 1,1

gasForNextCity = 1,1

Any index is correct, start at city 0 we will the tank with 1 unit of fuel, we spend 1 unit of fuel and reach city 1 with 0 fuel left. We fill the tank there with 1 unit of fuel, spend 1 unit of fuel to go to the next city which bring us back to the start and end our journey.

gasAtCity = 1,1

gasForNextCity = 2,2

No city is correct since no matter where we start, we won't ever have enough fuel in the tank to reach the next city.

gasAtCity = 1,1,2

gasForNextCity = 1,2,1

Start from last city is the only possible choice as starting from earlier places will leave us at some point with not enough fuel to continue the trip.

With the given problem, the fact that there are two arrays and they are circular might cause some confusion.

However, we can notice a trip can be completed if and only if there exists a start point such that the fuel in our tank never falls below zero while we cross all cities.

Given this observation, we can then simplify the problem to:

• finding whether such trip is possible
• if possible, finding where to start

To determine if the trip is possible we sum all the values from gasAtCity and subtract all the values from gasForNextCity, if the result is greater than or equal to zero, there is at least one path that does not violate our requirement.

Once we know a path exists, we can choose the first city as start point, then walk our array, updating our fuel correctly at each step.

If we ever reach a point where the fuel count would be negative, it means there is no path from our start, so we choose the NEXT city as start point of our path (some similarities with Kadane's maximum subarray sum logic).

Since we know a path exists, the first city that does not violate our requirement (fuel in the tank never goes below zero when moving OUT of that city), is a valid answer.

We also notice that there is no need to calculate whether the trip is possible beforehand, we can instead in a single pass track which city we'd use as start IF the trip was possible AND track the rolling sum of the tank fuel from first to last city.

At the end, IF the rolling sum is NOT negative, then the start we chose is our answer, otherwise we return -1.

Example:

gasAtCity = 1,1,1,1,1

gasForNextCity = 1,1,2,1,1

With our logic alone, we'd consider city at position 3 to be a valid start.

That is true ONLY if we know such trip is possible (meaning from there the rolling sum including other cities will never fall below zero).

So by also checking the rolling sum, we'd recognize that situation and return -1 instead.

Total complexity is O(N) and space is O(1)

You can check my implementation of startIndexForSumNeverBelowZero on my Gist along with some tests in StartIndexForSumNeverBelowZeroJTests.