Skip to main content
Talentd

Minimum Time to Complete Trips - Solution & Explanation

MediumArrayBinary Search17 min readAsked at: Amazon, Meta, Uber +2
Practice this problem

Problem Statement

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 <= 105
  • 1 <= time[i], totalTrips <= 107

Approach Overview

Problem 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 1: Binary Search on Time

This approach uses binary search to find the minimum time required for the buses to make at least the specified number of trips. The key observation is that if at time `t`, the buses can complete the required trips, then they can also do it in any time greater than `t`. Conversely, if they cannot make the required number of trips at time `t`, then they cannot do it in any lesser time.

We employ binary search with an initial low of 1 and a high value calculated as the maximum possible trip time multiplied by the required total trips. For each midpoint, we calculate the number of trips that all buses can make and adjust the time bounds based on whether the trips meet the requirement or not.

First, we define a helper function canCompleteTrips that verifies if the current time allows the buses to complete the total desired trips. In the main function, we perform binary search on the possible time interval. For each midpoint, we check the fulfillment of the total trips and adjust our search space accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log(maxTime)), where 'n' is the number of buses and 'maxTime' is the maximum possible time.
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Binary Search

We notice that if we can complete at least totalTrips trips in t time, then we can also complete at least totalTrips trips in t' > t time. Therefore, we can use the method of binary search to find the smallest t.

We define the left boundary of the binary search as l = 1, and the right boundary as r = min(time) times totalTrips. For each binary search, we calculate the middle value mid = \frac{l + r}{2}, and then calculate the number of trips that can be completed in mid time. If this number is greater than or equal to totalTrips, then we reduce the right boundary to mid, otherwise we increase the left boundary to mid + 1.

Finally, return the left boundary.

The time complexity is O(n times log(m times k)), where n and k are the length of the array time and totalTrips respectively, and m is the minimum value in the array time. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search on Time

Time Complexity: O(n log(maxTime)), where 'n' is the number of buses and 'maxTime' is the maximum possible time.
Space Complexity: O(1).

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Time SimulationO(n * T)O(1)Conceptual baseline for understanding the problem; impractical for large inputs
Binary Search on TimeO(n log T)O(1)Optimal solution when trips increase monotonically with time

Video Solution

Minimum Time to Complete Trips | Leetcode 2187 | Detailed | codestorywithMIK • codestorywithMIK • 16,794 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Time to Complete Trips easy or hard?
Minimum Time to Complete Trips is classified as a Medium problem. The implementation is short, but recognizing the binary search on answer pattern requires experience with monotonic search spaces and optimization problems.
Minimum Time to Complete Trips Python/Java solution
Most implementations use the same binary search logic regardless of language. Define a helper check that sums mid // time[i] across the array, then adjust the search range. The approach translates cleanly to Python, Java, C++, JavaScript, and C#.
How to solve Minimum Time to Complete Trips in O(n log T)?
Use binary search over the time range. Set left = 1 and right = min(time) * totalTrips. For each midpoint, compute total trips as sum(mid / time[i]). If the trips are at least totalTrips, move the right boundary left; otherwise move the left boundary right. The smallest valid time is the answer.
What is the best approach for Minimum Time to Complete Trips?
Binary Search on Time is the optimal approach. The number of trips completed grows monotonically as time increases, which allows searching for the smallest feasible time. Each binary search step calculates total trips by summing timeCandidate / time[i] across all buses, giving O(n log T) complexity.
Is Minimum Time to Complete Trips asked at Google/Amazon/Meta?
This style of problem frequently appears in interviews at large tech companies because it tests binary search on the answer pattern. Variations of scheduling and minimum feasible time problems have been reported in interviews at Amazon, Google, and other large tech firms.
What data structure is used in Minimum Time to Complete Trips?
The problem mainly uses arrays and a binary search algorithm. The array stores bus trip durations, and each binary search step iterates through the array to compute how many trips can be completed within a candidate time.
What is the time complexity of Minimum Time to Complete Trips?
The optimal algorithm runs in O(n log T) time, where n is the number of buses and T is the maximum possible time bound (often min(time) * totalTrips). Each binary search step scans the array once to compute completed trips. Space complexity is O(1).

Ready to solve this problem?

Practice Minimum Time to Complete Trips with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Candies Allocated to K Children

Next

Maximum Number of Robots Within Budget