Leetcode 2187 || Minimum Time to Complete Trips

Problem Link

https://leetcode.com/problems/minimum-time-to-complete-trips/description/

Discussion & Solution

In this problem, an array of times is given along with totalTrips. Each number of the given array denotes how much time ith bus needs to complete a trip. And we have to find a solution to complete totatTrips within minimum time.

Look at some examples below to understand the problem better :

ex 01:
Input : time = [1,2,3], totalTrips = 5
Output : 3
Explanation : 
                 [1,2,3]
t = 1 -> trips = 1+0+0 = 1
t = 2 -> trips = 2+1+0 = 2
t = 3 -> trips = 3+1+1 = 5 --> totalTrips

ex 01:
Input : time = [10,5,3,6,2], totalTrips = 7
Output : 6
Explanation : 
                [10,5,3,6,2]
t = 2 -> trips = 0+0+0+0+1 = 1
t = 3 -> trips = 0+0+1+0+1 = 2
t = 4 -> trips = 0+0+1+0+2 = 3
t = 5 -> trips = 0+1+1+0+2 = 4
t = 6 -> trips = 0+1+2+1+3 = 7 --> totalTrips

So, how do you think we should solve the problem?

Let's think of a general approach. Generally, we can think of a solution given below.

def minimumTime(time, totalTrips):
    t = 1
    while t:
        trips = 0
        for i in time:
            trips += t//i

        if trips>=totalTrips:
            return t
        t += 1

So we can start from t = 1. This will continue until we get a t where trips==totalTrips.

This solution is absolutely fine. The only problem is, we don't know how many times the while loop needs to be run. Each time we have to iterate through the time array. Here, the time complexity is O(t*n). So you will get a Time Limit Exceeded error easily.

How can we reduce the time complexity?

So if we get to know the range of t and search within its range, it could be easier to find a solution. If we implement a search algorithm, we'll be able to reduce our code's time complexity, right?

As you may know, already there is a search algorithm, Binary Search. The complexity of this algorithm is O(log n). So now we will implement binary search to find out our desired solution.

Let's find out the range of t first.

If we want to complete at least one trip, the minimum value of tshould be min(time) - minimum of the given time array.

And what could be the worst case? The solution would take the highest amount of time if the maximum value of the given array has to complete all the trips. So t = max(time)*totalTrips is the upper bound of t .

Let's jump into code :

def minimumTime(time, totalTrips):
    if len(time)==1:
        return totalTrips*time[0]

    minn = min(time)
    maxx = max(time)*totalTrips
    count = 0
    while minn<maxx:
        mid = minn+(maxx-minn)//2
        t = 0
        for i in time:
            t += mid//i

        if t>=totalTrips:
            maxx = mid
        else:
            minn = mid+1

    return minn

So after implementing binary search, the time complexity is reduced to O(log (maxx-minn)*n) and you can reduce it a tiny bit by breaking the for loop when t>=totalTrips.

It is a more efficient solution than the general one we thought of first.

Let me know if you have a more efficient solution or any questions or confusion or if you like this article.

Thanks for reading this far. Happy coding!