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

Imo this is very easy

1. Loop through every pump
2. Check if a pump has more petrol than the kilometer (1st condition)
3. Test that pump. If during the tour, the remaining fuel >= 0 (2nd condition)
4. Return index of the pump that passed 2 conditions note: remaining fuel = fuel - distance (kilometer)

The challenge is how to test 2nd condition. If you want to test a pump number 2, than it need to go through [2 > 3 > 4 > 5 > 1] if there is 5 pumps. If during testing and that specific pump's remaining fuel get to below 0 than skip that pump

def truckTour(petrolpumps):

petrolRest = [pump[0]-pump[1] for pump in petrolpumps] * 2

for i in range(len(petrolpumps)):

    tank = 0

    for j in range(i, i + len(petrolpumps)):

        tank += petrolRest[j]

        if tank < 0: break     

    if tank < 0: continue

    else: return i

return -1

Python Solution

• def truckTour(petrolpumps):
• fuel=0
• pos=0
• for i in range(len(petrolpumps)):
• fuel+=petrolpumps[i][0]-petrolpumps[i][1]
• if fuel<0:
• fuel=0
• pos=i+1
• return pos