2187. Minimum Time to Complete Trips Solution

The problem

You are given an array time where time[i] denotes the time taken by the i^th 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 <= 10⁵
1 <= time[i], totalTrips <= 10⁷

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.

Python

def canCompleteTrips(time, t, totalTrips):
    trips = 0
    for bus_time in time:
        trips += t // bus_time
        if trips >= totalTrips:
            return True
    return trips >= totalTrips

def minimumTime(time, totalTrips):
    low, high = 1, int(1e14)
    result = high
    while low <= high:
        mid = low + (high - low) // 2
        if canCompleteTrips(time, mid, totalTrips):
            result = mid
            high = mid - 1
        else:
            low = mid + 1
    return result

# Example usage
if __name__ == '__main__':
    time = [1, 2, 3]
    totalTrips = 5
    print(minimumTime(time, totalTrips))

Java

import java.util.*;

public class MinTimeToCompleteTrips {
    private static boolean canCompleteTrips(int[] time, long t, int totalTrips) {
        long trips = 0;
        for (int busTime : time) {
            trips += t / busTime;
            if (trips >= totalTrips) return true;
        }
        return trips >= totalTrips;
    }

    public static int minimumTime(int[] time, int totalTrips) {
        long low = 1, high = (long) 1e14;
        int result = (int) high;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (canCompleteTrips(time, mid, totalTrips)) {
                result = (int) mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] time = {1, 2, 3};
        int totalTrips = 5;
        System.out.println(minimumTime(time, totalTrips));
    }
}

C++

#include <iostream>
#include <vector>

bool canCompleteTrips(const std::vector<int>& time, long long t, int totalTrips) {
    long long trips = 0;
    for (const int& busTime : time) {
        trips += t / busTime;
        if (trips >= totalTrips) return true;
    }
    return trips >= totalTrips;
}

int minimumTime(std::vector<int>& time, int totalTrips) {
    long long low = 1, high = 1LL * 1e14;
    int result = high;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (canCompleteTrips(time, mid, totalTrips)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    std::vector<int> time = {1, 2, 3};
    int totalTrips = 5;
    std::cout << minimumTime(time, totalTrips) << std::endl;
    return 0;
}

JavaScript

function canCompleteTrips(time, t, totalTrips) {
    let trips = 0;
    for (const busTime of time) {
        trips += Math.floor(t / busTime);
        if (trips >= totalTrips) return true;
    }
    return trips >= totalTrips;
}

function minimumTime(time, totalTrips) {
    let low = 1, high = 1e14;
    let result = high;
    while (low <= high) {
        const mid = Math.floor(low + (high - low) / 2);
        if (canCompleteTrips(time, mid, totalTrips)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

// Example usage
const time = [1, 2, 3];
const totalTrips = 5;
console.log(minimumTime(time, totalTrips));

#include <stdio.h>

int canCompleteTrips(int* time, int timeSize, long long t, int totalTrips) {
    long long trips = 0;
    for (int i = 0; i < timeSize; i++) {
        trips += t / time[i];
        if (trips >= totalTrips) return 1;
    }
    return trips >= totalTrips;
}

int minimumTime(int* time, int timeSize, int totalTrips) {
    long long low = 1, high = 1LL * timeSize * 1e7;
    int result = high;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (canCompleteTrips(time, timeSize, mid, totalTrips)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int time[] = {1, 2, 3};
    int totalTrips = 5;
    printf("%d\n", minimumTime(time, 3, totalTrips));
    return 0;
}

using System;

class MinTimeToCompleteTrips {
    private static bool CanCompleteTrips(int[] time, long t, int totalTrips) {
        long trips = 0;
        foreach (int busTime in time) {
            trips += t / busTime;
            if (trips >= totalTrips) return true;
        }
        return trips >= totalTrips;
    }

    public static int MinimumTime(int[] time, int totalTrips) {
        long low = 1, high = (long)1e14;
        int result = (int)high;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (CanCompleteTrips(time, mid, totalTrips)) {
                result = (int)mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }

    public static void Main(string[] args) {
        int[] time = { 1, 2, 3 };
        int totalTrips = 5;
        Console.WriteLine(MinimumTime(time, totalTrips));
    }
}

The Python implementation follows the same logic with the canCompleteTrips function checking the number of trips completed for a given time. Binary search is utilized to find the optimal solution.

Complexity

Time Complexity: O(n log(maxTime)), where 'n' is the number of buses and 'maxTime' is set as 10^14.
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).

TypeScript

function minimumTime(time: number[], totalTrips: number): number {
    let left = 1n;
    let right = BigInt(Math.min(...time)) * BigInt(totalTrips);
    while (left < right) {
        const mid = (left + right) >> 1n;
        const cnt = time.reduce((acc, v) => acc + mid / BigInt(v), 0n);
        if (cnt >= BigInt(totalTrips)) {
            right = mid;
        } else {
            left = mid + 1n;
        }
    }
    return Number(left);
}

func minimumTime(time []int, totalTrips int) int64 {
	mx := slices.Min(time) * totalTrips
	return int64(sort.Search(mx, func(x int) bool {
		cnt := 0
		for _, v := range time {
			cnt += x / v
		}
		return cnt >= totalTrips
	}))
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Binary Search on Time	Time Complexity: O(n log(maxTime)), where 'n' is the number of buses and 'maxTime' is set as 10^14. Space Complexity: O(1).
Binary Search	–

Complexity analysis

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

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).

Minimum Time to Complete Trips solution and explanation

The problem

Approach overview

Approach 1: Binary Search on Time

Approach 2: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Time to Complete Trips solution and explanation

The problem

Approach overview

Approach 1: Binary Search on Time

Approach 2: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems