We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Truck Tour
  5. Discussions

Truck Tour

  • al_bayona
     + 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