Start learning free

LESSON 283 OF 438 · BINARY SEARCH

Uber Rides in Java: Binary Search on the Answer in O(m log T)

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

    JAVA · BINARY SEARCH

    Uber Rides in Java, explained

    Problem overview

    You get an int[] named cabTripTime, where element i is the number of minutes the i-th cab needs for one trip, and a number of trips n. The cabs drive at the same time, and each one starts its next trip as soon as it finishes the previous one. minTime returns the smallest number of minutes after which at least n trips are done in total.

    For n = 3 and cabTripTime = [1, 2] the answer is 2. After 1 minute the first cab has finished 1 trip and the second none. After 2 minutes the first has finished 2 and the second 1, which makes 3. For n = 10 and [1, 3, 5, 7] the answer is 7: after 6 minutes the cabs have finished 6 + 2 + 1 + 0 = 9 trips, after 7 minutes 7 + 2 + 1 + 1 = 11.

    A cab with a trip time of 0 finishes any number of trips instantly, so the answer is 0 then. The statement asks for O(m log T) time, where m is the number of cabs and T = n * min(cabTripTime), and for O(1) extra space.

    Approach: binary search on the time

    Handing out trips to cabs one at a time would take about n steps, and n can reach two million. Flip the question instead: given a time t, can the cabs finish n trips within t minutes? A cab with trip time v finishes t / v whole trips, because integer division drops an unfinished trip, and the cabs work in parallel, so their counts add up.

    If t minutes are enough, so are t + 1, since cabs only finish more trips as time passes. The answers therefore run no, no, no, yes, yes, yes, and the task is to find the first yes. Binary search does this by testing the middle time and discarding the half that cannot hold the first yes.

    The range is 1 to n * min(cabTripTime). The upper end always works: the fastest cab alone finishes n trips in that time. There are about log T rounds, and each one makes a pass over the m cabs.

    For n = 3 and [1, 2] the range is 1 to 3. The middle, 2, gives 2 + 1 = 3 trips, which is enough, so record 2 and search 1 to 1. Time 1 gives 1 trip, which is not enough, so the answer is 2.

    Step by step

    The lesson provides minTime, which does the binary search, and asks you to write the helper it calls.

    1. Declare boolean hasSolution(int[] cabTripTime, int n, int time) above minTime, and write its closing brace at once. It answers: can the cabs finish n trips within time minutes?
    2. Create a counter s, a long, starting at 0. It counts the trips all cabs finish. Why it is a long is explained after the solution.
    3. Open the loop over the cabs: a for-each over cabTripTime with an int named v, the minutes one trip of that cab takes. Write its closing brace at once.
    4. Inside the loop, add time / v to s. Dividing two ints drops the fraction, so a trip that isn't finished doesn't count.
    5. After the loop, return s >= n. true means that time is enough, so the search tries a shorter time. false means it needs a longer one.

    In minTime, the search finds the smallest trip time, sets left = 1 and right = n * minTime, and loops while left <= right. If the middle time is enough, it is recorded in result and the search continues on the shorter half (right = mid - 1), in case an earlier time also works. Otherwise it moves to the longer half (left = mid + 1). The last recorded time is the smallest one that works.

    The solution in Java

    class Solution {
    
    boolean hasSolution(int[] cabTripTime, int n, int time) {
        long s = 0;
        for (int v : cabTripTime) {
            s += time / v;
        }
        return s >= n;
    }
    
    public int minTime(int[] cabTripTime, int n) {
        int minTime = Arrays.stream(cabTripTime).min().getAsInt();
        int result = 0, left = 1, right = n * minTime;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (hasSolution(cabTripTime, n, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

    The Java details worth knowing:

    • The counter is a long. An int that goes past 2,147,483,647 wraps around to a negative number without any error. The counter adds up the trips of every cab, so it can get far beyond that. With a million cabs that each take 1 minute, a time of 1,000,000 minutes gives 1,000,000,000,000 trips: an int counter ends that loop at -727379968, a long at 1000000000000. With those cabs and n = 2000000, minTime returns 2, while the same code with an int counter returns 1142464.
    • Mixed arithmetic. In s += time / v the division is done in int, which truncates, and the result is then widened to long for the addition. In s >= n, n is widened to long automatically.
    • Division by zero throws. An int division by 0 throws an ArithmeticException. The solution never divides by a zero trip time: then minTime is 0, so right is 0, left <= right is false at once, and the method returns 0 without calling hasSolution.
    • Arrays.stream(cabTripTime).min().getAsInt(). Streaming an int[] gives an IntStream. Its min() returns an OptionalInt, and getAsInt() unwraps it. It would throw on an empty array, which the constraints rule out. The class needs java.util.Arrays imported when you compile it as a standalone file.
    • (left + right) >> 1 halves a non-negative int by shifting one bit. With right at most 200 million, the sum fits in an int.
    • Several declarations on one line. int result = 0, left = 1, right = n * minTime; declares three int variables.

    Complexity

    Let m be the number of cabs and T = n * min(cabTripTime).

    Time: O(m log T). The range has T values and halves every round, so there are about log T rounds. Each round calls hasSolution, which makes one pass over the m cabs. Finding the minimum first costs one more pass, O(m).

    Space: O(1). The code keeps a handful of numbers and does not copy the array.

    Edge cases and common mistakes

    • A cab with trip time 0. [0, 5] with n = 10 returns 0.
    • One cab. [5] with n = 4 returns 20: the cab does its four trips one after another.
    • One trip. [3, 3, 3] with n = 1 returns 3.
    • Cabs that finish together. [2, 3] with n = 5 returns 6: after 6 minutes the cabs have done 3 + 2 = 5 trips, and after 5 minutes only 2 + 1 = 3.
    • Very many cabs. A million cabs with trip time 1 and n = 2000000 return 2. A counter that is too small wraps and breaks this case.
    • Stopping at the first true. When hasSolution says yes, a smaller time may also work. Record mid and keep searching the shorter half.
    • Counting a partial trip. A cab with trip time 3 has finished 1 trip at minute 5, not 2. Rounding up would count unfinished trips.
    • Using left < right. A range with a single value would never be tested. Keep <=.

    Testing

    • n = 3, [1, 2] gives 2.
    • n = 10, [1, 3, 5, 7] gives 7.
    • n = 10, [0, 5] gives 0.
    • n = 4, [5] gives 20.
    • n = 5, [2, 3] gives 6.
    • n = 10000, [20000] gives 200000000.
    • n = 2000000 with one million cabs that each take 1 minute gives 2.
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free