Minimum Time to Complete Trips

Hard
834.

Minimum Time to Complete Trips

Minimum Time to Complete Trips is a hard coding problem on arrays and binary search, asked in Amazon, Google and Ola interviews.

Bus i takes time[i] units per trip and starts its next trip immediately. Buses run independently.

Return the minimum time for the fleet to complete at least totalTrips trips in total.

Example 1

Input
time = [1,2,3], totalTrips = 5
Output
3
Explanation
By t = 3 the buses have done 3, 1 and 1 trips.

Example 2

Input
time = [2], totalTrips = 1
Output
2

Example 3

Input
time = [5,10,10], totalTrips = 9
Output
25

Constraints

  • 1 <= time.length <= 100000
  • 1 <= time[i] <= 1000000
  • 1 <= totalTrips <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} time
 * @param {number} totalTrips
 * @return {number}
 */
var minimumTime = function(time, totalTrips) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Time to Complete Trips — Problem & Solution

Minimum Time to Complete Trips solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Time to Complete Trips is a hard coding problem on arrays and binary search, asked in Amazon, Google and Ola interviews.

  • Difficulty: Hard
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, Ola
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Bus i takes time[i] units per trip and starts its next trip immediately. Buses run independently.

Return the minimum time for the fleet to complete at least totalTrips trips in total.

Example 1

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation: By t = 3 the buses have done 3, 1 and 1 trips.

Example 2

Input: time = [2], totalTrips = 1
Output: 2

Example 3

Input: time = [5,10,10], totalTrips = 9
Output: 25

Constraints

  • 1 <= time.length <= 100000
  • 1 <= time[i] <= 1000000
  • 1 <= totalTrips <= 1000

Hints for Minimum Time to Complete Trips

  1. Hint 1

    By time t, bus i has completed floor(t / time[i]) trips — a non-decreasing function of t.

  2. Hint 2

    So the total is non-decreasing too, and binary search applies.

  3. Hint 3

    An upper bound is the fastest bus doing every trip alone.

How to solve Minimum Time to Complete Trips

Binary search the elapsed time. The fleet's trip count at time t is a simple sum of floors, and it only grows with t, so the first t reaching totalTrips is the answer.

Approach

  1. Bound the search by [1, min(time) · totalTrips] — the fastest bus alone always suffices by then.
  2. trips(t): sum floor(t / time[i]), stopping early once the target is reached.
  3. Binary search the smallest t with trips(t) >= totalTrips.

Why it works

Each bus's trip count is a step function of t, non-decreasing, so their sum is too — the predicate flips exactly once. The upper bound holds because by min(time) · totalTrips the fastest bus has done totalTrips trips on its own, so the fleet has done at least that many.

Complexity

  • Time — O(n log(min(time) · totalTrips))
  • Space — O(1)

Pitfalls

  • The partial sums reach 10^5 · 10^9 before the early exit — accumulate in 64-bit or stop as soon as the target is met.
  • Searching up to the slowest bus times totalTrips still works but wastes iterations.
  • Buses are independent; there is no scheduling to do.

Reference solution

Python

from typing import List

def minimumTime(time: List[int], totalTrips: int) -> int:
    lo, hi = 1, min(time) * totalTrips

    def trips(t: int) -> int:
        c = 0
        for x in time:
            c += t // x
            if c >= totalTrips:
                return c
        return c

    while lo < hi:
        mid = (lo + hi) // 2
        if trips(mid) >= totalTrips:
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

private static long tripsBy(int[] time, int totalTrips, long t) {
    long c = 0;
    for (int x : time) {
        c += t / x;
        if (c >= totalTrips) return c;
    }
    return c;
}

public static int minimumTime(int[] time, int totalTrips) {
    int fastest = time[0];
    for (int x : time) fastest = Math.min(fastest, x);
    long lo = 1, hi = (long) fastest * totalTrips;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (tripsBy(time, totalTrips, mid) >= totalTrips) hi = mid; else lo = mid + 1;
    }
    return (int) lo;
}

C++

static long long tripsBy(vector<int>& time, int totalTrips, long long t) {
    long long c = 0;
    for (int x : time) {
        c += t / x;
        if (c >= totalTrips) return c;
    }
    return c;
}

int minimumTime(vector<int>& time, int totalTrips) {
    int fastest = time[0];
    for (int x : time) fastest = min(fastest, x);
    long long lo = 1, hi = (long long) fastest * totalTrips;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (tripsBy(time, totalTrips, mid) >= totalTrips) hi = mid; else lo = mid + 1;
    }
    return (int) lo;
}

JavaScript

var minimumTime = function(time, totalTrips) {
    var fastest = time[0], i;
    for (i = 1; i < time.length; i++) if (time[i] < fastest) fastest = time[i];
    var trips = function(t) {
        var c = 0;
        for (var j = 0; j < time.length; j++) {
            c += Math.floor(t / time[j]);
            if (c >= totalTrips) return c;
        }
        return c;
    };
    var lo = 1, hi = fastest * totalTrips;
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (trips(mid) >= totalTrips) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search