Start learning free

LESSON 287 OF 442 · BINARY SEARCH

Uber Rides in Kotlin: Binary Search on the Answer

Practice O(n log T) Read the full explanation

Uber has several cabs. The ith cab takes cabTripTime[i] minutes to complete any trip. Your task is to find the minimum time it will take Uber to get n trips completed with these cabs. You can assume there is no waiting time in-between the trips.

Note: Different cabs can take trips simultaneously (at any time, there can be more than one cab with an ongoing trip)

Example 1:

Input: n = 3, cabTripTime = [1, 2]
Output: 2
Explanation:
Trips can be managed like this:
- Trip 1: first cab from t = 0 to t = 1;
- Trip 2: second cab from t = 0 to t = 2;
- Trip 3: first cab from t = 1 to t = 2.

All the trips can be completed in 2 minutes. In 1 minute the cabs finish only 1 + 0 = 1 trip, so the answer is 2.

Example 2:

Input: n = 10, cabTripTime = [1, 3, 5, 7]
Output: 7
Explanation:
Trips can be managed like this:
- Trip 1: 1st cab from t = 0 to t = 1;
- Trip 2: 2nd cab from t = 0 to t = 3;
- Trip 3: 3rd cab from t = 0 to t = 5;
- Trip 4: 4th cab from t = 0 to t = 7;
- Trip 5: 1st cab from t = 1 to t = 2;
- Trip 6: 1st cab from t = 2 to t = 3;
- Trip 7: 1st cab from t = 3 to t = 4;
- Trip 8: 2nd cab from t = 3 to t = 6;
- Trip 9: 1st cab from t = 4 to t = 5;
- Trip 10: 1st cab from t = 5 to t = 6.

All the trips can be completed in 7 minutes. In 6 minutes the cabs finish at most 6 + 2 + 1 + 0 = 9 trips, so the answer is 7.

Constraints:

  • 1 <= cabTripTime.length <= 106
  • 0 <= cabTripTime[i] <= 2 * 104
  • 1 <= n <= 2 * 106
  • n * min(cabTripTime) <= 2 * 108
  • A cab whose trip time is 0 finishes any number of trips instantly, so then the answer is 0.

Note:

Your algorithm should run in O(m log T) time, where m is the number of cabs and T = n * min(cabTripTime) is the longest time worth trying, and use O(1) extra space.


STEP 1 OF 5
    Ctrl + Enter to check

    KOTLIN · BINARY SEARCH

    Uber Rides in Kotlin, explained

    Problem overview

    A company has several cabs, and the cab at index i needs cabTripTime[i] minutes for any trip. The function minTime receives the IntArray cabTripTime and the number of trips n, and returns the smallest number of minutes in which n trips can be completed. The cabs work at the same time, and a cab starts its next trip the moment it finishes the previous one.

    For n = 3 and [1, 2] the answer is 2. After 1 minute only the first cab has finished a trip, which makes 1 trip. After 2 minutes the first cab has finished 2 trips and the second cab 1, which makes 3.

    For n = 10 and [1, 3, 5, 7] the answer is 7. After 6 minutes the cabs finish 6 + 2 + 1 + 0 = 9 trips, which is one short. After 7 minutes they finish 7 + 2 + 1 + 1 = 11.

    The statement asks for O(m log T) time, where m is the number of cabs and T is n times the fastest trip time, and for O(1) extra space.

    Approach: search over the time, not over the trips

    Simulating the cabs trip by trip would take about n steps, and n reaches two million. Instead, flip the question. Instead of asking how long n trips take, ask whether t minutes are enough. That question is easy to answer: a cab with trip time v finishes t / v whole trips in t minutes, rounded down because an unfinished trip doesn't count, and the cabs' counts add up.

    The answer to "are t minutes enough?" has a useful shape. If 7 minutes are enough, 8 are enough too, since the cabs only finish more trips. So as t grows, the answers go from "no, no, no" to "yes, yes, yes". The smallest t that gives "yes" is the one wanted, and binary search finds it in about log T checks.

    The search needs a range. The lower end is 1 minute. For the upper end, the fastest cab alone finishes n trips in n * minTrip minutes, so that time is always enough, and T = n * minTrip can serve as the largest time worth trying. Each check costs one pass over the m cabs, which gives the O(m log T) bound.

    Step by step

    The lesson provides the binary search in minTime and asks you to write the check, a helper called hasSolution.

    1. Add hasSolution(cabTripTime: IntArray, n: Int, time: Int): Boolean. It answers: can the cabs finish n trips within time minutes? minTime calls it with a middle time, then searches the shorter or the longer half.
    2. Create the counter s with var, starting at 0L, so it is a Long. It counts the trips all cabs finish in time minutes. The notes after the solution explain why it needs 64 bits.
    3. Open the loop over the cabs with for (v in cabTripTime) and write its closing brace at once. The variable v is the trip time of one cab.
    4. Inside the loop, add time / v to s. Dividing two Int values drops the fraction, so a trip that isn't finished doesn't count. The cabs drive in parallel, so their counts are added.
    5. Return s >= n. true means that time is enough, so the search tries a shorter time. false means it needs a longer one.

    The search in minTime does the rest. It finds the fastest trip time, minTrip, and sets the search range from left = 1 to right = n * minTrip. In each round it checks the middle time. If the middle time is enough, it records it in result and looks at the shorter half, right = mid - 1. If not, it moves to the longer half, left = mid + 1. The last recorded time is the smallest one that works.

    The solution in Kotlin

    class Solution {
    fun hasSolution(cabTripTime: IntArray, n: Int, time: Int): Boolean {
        var s = 0L
        for (v in cabTripTime) {
            s += time / v
        }
        return s >= n
    }

    fun minTime(cabTripTime: IntArray, n: Int): Int {
        var minTrip = cabTripTime[0]
        for (v in cabTripTime) {
            minTrip = minOf(minTrip, v)
        }
        var result = 0
        var left = 1
        var right = n * minTrip
        while (left <= right) {
            val mid = (left + right) / 2
            if (hasSolution(cabTripTime, n, mid)) {
                result = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return result
    }
}

    The Kotlin details worth a closer look:

    • Integer division. time / v with two Int values truncates, so 7 / 3 is 2. That is exactly the number of whole trips.
    • Division by zero. time / 0 throws an ArithmeticException for Int. A trip time of 0 never reaches the division: then minTrip is 0, right is 0 and the loop doesn't run, so minTime returns 0, which is the right answer when a cab finishes trips instantly.
    • Int limits. n * minTrip is at most 200 million by the constraints, and left + right at most 400 million, so the midpoint can't overflow. The counter s is different: it adds up counts from every cab, so it is a Long, written 0L. With a million cabs that each take 1 minute, a time of 1,000,000 minutes gives 1,000,000,000,000 trips. That is far beyond the Int limit of 2,147,483,647: an Int counter would hold -727379968 after that loop, while the Long holds 1000000000000. In s += time / v the Int result of the division is widened to Long before it is added, and s >= n compares a Long with an Int without a cast. With these million cabs and n = 2000000, minTime returns 2.
    • minOf. This standard-library function returns the smaller of two values, so the loop keeps the smallest trip time seen so far.
    • A for loop over an IntArray. for (v in cabTripTime) reads the elements directly, without indices.
    • Function parameters are read-only. The code changes left, right and result, which are local var variables, and never the parameters.

    Complexity

    Let m be the number of cabs and T = n * minTrip.

    Time: O(m log T). The search halves the range from T down to nothing, so it makes about log T rounds. Each round calls hasSolution, which makes one pass over m cabs. Finding minTrip costs one more pass, O(m).

    Space: O(1). Only a handful of integers are stored.

    Edge cases and common mistakes

    • One cab. [5] with n = 4 returns 20: the lone cab does the four trips one after another.
    • One trip. [2, 2, 2] with n = 1 returns 2, since the first trip needs the full 2 minutes on any cab.
    • A cab with trip time 0. [0, 3] with n = 4 returns 0.
    • Counting a partial trip. A cab that is halfway through a trip hasn't completed anything. Rounding up would count it and give answers that are too small.
    • Returning the wrong end of the search. The answer is the smallest time that works, so a successful check moves right down, and the time is recorded before that. If you move left up on a success, you end up with the largest time tried, which is too big.
    • Using left < right. When the range is a single time, it would be skipped, and a correct answer could be missed.

    Testing

    • cabTripTime = [1, 2], n = 3 gives 2.
    • cabTripTime = [1, 3, 5, 7], n = 10 gives 7.
    • cabTripTime = [5], n = 4 gives 20.
    • cabTripTime = [0, 3], n = 4 gives 0.
    • cabTripTime = [20000], n = 10000 gives 200000000.
    • One million cabs that each take 1 minute, n = 2000000, gives 2. This is the case that needs the Long counter.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free