I recently came across a similar problem where I had to figure out the best starting point for a petrol pump tour on a circle. After some thinking, I realized that it's like solving a puzzle, much like in games. It reminded me of TruckersofEuropeAPK, a modified version of Truckers of Europe 3, where you're tasked with transporting cargo across European cities, just like the truck in this problem. In TruckersofEuropeAPK, all the premium features are unlocked, and it’s as if you’re calculating the best route in real life. Definitely a cool experience if you're into driving simulation games!

Save the previous circle you already calculated, in a way you can speed it up via memoization. After each pump you can add that pump's total cost to the cost of the pumps before it. Using this strategy you will never have to recalclate the beginning of the loop.

There's probably other ways to optimize it, but I got lazy after memoizing the beginning part of the loop. This way you never have to worry about trying to loop back your array around.

Im getting an error with this:int fuel = 0; int miles = 0; int index = 0; for (int i = 0; i < petrolpumps.size(); i++) { fuel += petrolpumps.get(i).get(0); miles += petrolpumps.get(i).get(1); if (fuel < miles) { fuel = 0; miles = 0; index = i + 1; } } return index; However if I change the inequality to this "if (fuel - miles < 0)" ,it is passing all the test cases. They are both supposed to be the same according to linear inequalities. This is math defying. Please help.

The problem is misleading, as it does not crearly states that there will always be a solution. You are led to believe to check if you go the full circle. You usually are taught to think of all scenarios, including no solution. So this was a very vague problem description. Finally, I was able to do it by using a prefix list in O(n) time, by using tabulation to optimize checking all the posible circles.

def truckTour(petrolpumps):
    _prefix = [ x[0] - x[1] for x in petrolpumps]
    _min = [0] * len(_prefix)
    _min2 = [0] * len(_prefix)

    print(_prefix)

    for i in range(1, len(_prefix)):
        _prefix[i] += _prefix[i-1]

    for i in range(len(_prefix)):
        if i == 0:
            _min[-(i+1)] = _prefix[-(i+1)]
            _min2[i] = _prefix[i]
        else:
            _min[-(i+1)] = min(_min[-i], _prefix[-(i+1)])
            _min2[i] = min(_min2[i-1], _prefix[i])

    # print(_prefix)
    # print(_min)
    # print(_min2)



    if _min[0] > 0:
        return 0

    for i, n in enumerate(_prefix):
        if i > 0:
            if _min[i] - _prefix[i-1] > 0 and _min2[i] + _prefix[-1] - _prefix[i-1] > 0:
                print(i)
                return i