• + 0 comments

    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