Watch 10 video solutions for Minimum Time to Complete Trips, a medium level problem involving Array, Binary Search. This walkthrough by codestorywithMIK has 14,774 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip.
Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.
You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.
Example 1:
Input: time = [1,2,3], totalTrips = 5 Output: 3 Explanation: - At time t = 1, the number of trips completed by each bus are [1,0,0]. The total number of trips completed is 1 + 0 + 0 = 1. - At time t = 2, the number of trips completed by each bus are [2,1,0]. The total number of trips completed is 2 + 1 + 0 = 3. - At time t = 3, the number of trips completed by each bus are [3,1,1]. The total number of trips completed is 3 + 1 + 1 = 5. So the minimum time needed for all buses to complete at least 5 trips is 3.
Example 2:
Input: time = [2], totalTrips = 1 Output: 2 Explanation: There is only one bus, and it will complete its first trip at t = 2. So the minimum time needed to complete 1 trip is 2.
Constraints:
1 <= time.length <= 1051 <= time[i], totalTrips <= 107Problem Overview: You are given an array time where time[i] is how long the i-th bus takes to finish one trip. Each bus can run multiple trips back‑to‑back. The goal is to find the minimum time required for all buses combined to complete at least totalTrips trips.
The challenge is that time can grow extremely large. A direct simulation of every trip quickly becomes infeasible. The key observation is that the number of trips completed increases monotonically as time increases. That monotonic property allows an efficient search over the answer.
Approach 1: Brute Force Time Simulation (O(n * T), Space O(1))
Start from time = 1 and increase time step by step. At each moment, compute how many trips all buses could have finished so far. For a bus with duration t, the completed trips are currentTime / t. Sum this for every bus and stop once the total reaches totalTrips. While the logic is simple, the upper bound for time (T) can be extremely large when totalTrips is large. This makes the approach impractical for real constraints because it may require billions of iterations.
Approach 2: Binary Search on Time (O(n log T), Space O(1))
This problem fits perfectly with binary search on the answer. Instead of incrementing time one unit at a time, search for the smallest time value that allows completing at least totalTrips. Define a search range where left = 1 and right = min(time) * totalTrips. The right boundary represents the worst case where the fastest bus does all trips alone.
For each midpoint mid, calculate how many trips can be completed by summing mid / time[i] for every bus in the array. If the total trips are greater than or equal to totalTrips, the time is sufficient, so move the right boundary left to search for a smaller feasible time. Otherwise move the left boundary right because more time is needed.
The monotonic behavior makes this search reliable: if a certain time works, any larger time will also work. Binary search narrows the answer in log T steps, and each step scans the array once.
Recommended for interviews: Binary search on time is the expected solution. Interviewers want to see that you recognize the monotonic property and convert the optimization problem into a decision problem (can we finish trips within time X?). A quick brute force explanation shows baseline reasoning, but the optimized binary search demonstrates algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Time Simulation | O(n * T) | O(1) | Conceptual baseline for understanding the problem; impractical for large inputs |
| Binary Search on Time | O(n log T) | O(1) | Optimal solution when trips increase monotonically with time |