1870. Minimum Speed to Arrive on Time

MediumArrayBinary Search
Leetcode Link

Problem Description

You have a specific amount of time, hour, to commute to the office using a series of trains. Each segment of your journey has a fixed distance, and all segments must be completed sequentially. The key challenge is that trains can only leave at the start of each hour, meaning you might need to wait before boarding the next train. For instance, if a train ride takes 1.5 hours, a 0.5-hour wait is required before the next train departs. Your task is to determine the minimum train speed (in km/h) required to reach the office on time. This speed must be a positive integer, and if it's impossible to arrive on time, the function should return -1. The provided constraints ensure that the solution won't be higher than 10^7 and the hour won't have more than two decimals.

Intuition

The minimum speed to reach on time is not evidently clear and can range from 1 to 10^7. To find the minimum speed efficiently, we employ a binary search strategy. A binary search halves the potential search space by checking whether a particular condition (in this case, being able to make it to the office on time at a certain speed) is met or not.

Here's the thought process for arriving at the binary search solution:

  1. If a particular speed allows us to reach the office on time (hour or less), then any speed higher than this would also suffice. Conversely, any speed lower than a speed that does not make it on time is also inadequate.

  2. We define a check function to determine if the current speed is sufficient to reach on time, considering the waiting time between train rides. The last ride doesn't require any wait time.

  3. Using a binary search, we find the minimum speed at which the check function returns true. As speeds lower than this minimum won't help us arrive on time, we restrict our search to the range where we might meet the condition.

  4. We initiate a search range from 1 to 10^7 and repeatedly narrow it down using the check function until we pinpoint the minimum required speed.

  5. If we're unable to find a speed that allows for a timely arrival within the maximum speed limit, we return -1, indicating that it's not possible to be punctual.

The binary search is implemented using the bisect_left function from the Python library. It operates by taking the range as an iterable, the condition to check, and a key function, which in this case is the check function. It then finds the leftmost value in the sorted range that satisfies the condition.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution to the problem leverages the binary search algorithm, which is ideal for the scenario because of its ability to reduce the search space in half with each iteration. The objective of the binary search in this context is to discover the minimum integer speed so that the total travel time does not exceed the given hour.

Here's how the binary search is used to implement the solution:

  • Define a check function: This function accepts a speed and calculates the total time taken to travel all distances in the dist array at that speed. For all train segments except the last, the time is rounded up to the nearest integer to account for the rule that trains leave only at the beginning of every hour. For the last train segment, exact time can be used since you don't need to wait for another train after.

  • Binary search algorithm: We perform a binary search to find the appropriate speed using two boundaries denoted as left and right, initially set to 1 and 10^7 + 1 respectively. The algorithm iteratively narrows these boundaries until the optimal speed is found.

    • Initialization: We set our initial search interval from 1 to 10^7 + 1, to cover the entire range of possible speeds as per the problem's constraints.

    • Binary search loop: At each step of the loop, the midpoint of the current interval is computed and passed to the check function. Based on the function's output:

      • If the check is true, it means the current speed or any higher could be the solution; hence we narrow the search to the lower half of the interval (right = mid).

      • If the check is false, it means the current speed is too slow, so we narrow the search to the upper half of the interval (left = mid + 1).

    • Checking for impossibility: If it's determined that even the highest possible speed doesn't allow us to be on time (at after searching the entire interval), we conclude that it's impossible to reach on time and return -1.

  • Using bisect_left: The binary search is succinctly executed using the bisect_left function from the bisect module, which is applied to a range object representing our potential speeds. We use a lambda function as the key to the bisect_left, which internally applies the check function to the speeds to handle the binary search. The result is then adjusted by adding 1 to the speed since bisect_left finds the leftmost place where True could be inserted without changing the order.

  • Mathematical and logical operations: The algorithm uses integer division (math.ceil) to account for the waiting time at stations and leverages boolean conditions to implement the binary search logic.

To sum it up, the solution efficiently navigates through a potentially massive search space to find the minimum speed necessary for timely arrival, using binary search principles encapsulated in Python's bisect_left function.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Suppose we have the following input parameters:

  • Distances array dist = [5, 7, 3], representing the distances of each train segment of the journey.
  • Total time allowed hour = 2.5 hours to reach the office.

Now, let's walk through the binary search approach to find the minimum train speed required for the given journey:

  1. Initialization: We start with a potential speed range of 1 to 10^7 + 1. This means our left boundary is 1 and our right boundary is 10^7 + 1.

  2. First iteration of binary search:

    • The mid-speed is (1 + 10000001) / 2 = 5000001.
    • We check if a train at 5000001 km/h can reach within 2.5 hours.
    • We calculate the time for each segment at 5000001 km/h:
      • Segment 1: 5 / 5000001 hours - No need to round up because there is another segment after.
      • Segment 2: 7 / 5000001 hours - No need to round up because there is another segment after.
      • Segment 3: 3 / 5000001 hours - This is the last segment, we take the exact time.
    • We sum up these times and find that the total time taken is way less than 2.5 hours, so we set right to 5000001.

  3. Second iteration of binary search:

    • The new mid-speed is (1 + 5000001) / 2 = 2500001.
    • We perform the same check function for the new mid-speed.
    • Again, the speed is high enough to get us there in under 2.5 hours, so we adjust right to 2500001.

  4. Continuing the binary search:

    • We continue halving the interval and checking, bringing the left and right boundaries closer after each iteration.

  5. Final step:

    • Eventually, we narrow down to a range where moving left by one would cause check to yield false, and we settle on the right boundary as the minimum sufficient speed.

    • Suppose after multiple iterations, we find that at 10 km/h, check is false, but at 11 km/h, check is true. This tells us that 11 km/h is the minimum speed required to reach the office on time.

  6. Result:

    • The binary search terminates when left is equal to right, which means we've found the minimum train speed satisfying the conditions.
    • If no such speed allows arrival within 2.5 hours, our search boundaries would converge such that check always returns false, and we return -1.

In our example, by following the binary search algorithm steps, we would eventually find that the minimum speed required for the distances [5, 7, 3] to be covered within 2.5 hours is 11 km/h. This result is achieved without testing every speed from 1 to 10^7 individually.

Solution Implementation

1from bisect import bisect_left
2import math
3from typing import List
4
5class Solution:
6    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
7        # Helper function to check if a given speed is sufficient to arrive on time
8        def is_speed_sufficient(speed):
9            total_time = 0
10            for i, distance in enumerate(dist):
11                # For the last distance, we don't need to ceil as we can arrive exactly on time
12                if i == len(dist) - 1:
13                    total_time += distance / speed
14                else:  # For all others, we'll ceil to account for the fact that we can't travel partial units of distance in less than an hour
15                    total_time += math.ceil(distance / speed) 
16            return total_time <= hour
17
18        # Set the maximum possible speed based on constraints; here, arbitrarily set to 10^7
19        max_possible_speed = 10**7 + 1
20      
21        # Binary search to find the minimum sufficient speed [1, max_possible_speed) 
22        # We are adding 1 because `bisect_left` will return the position to insert True to maintain sorted order
23        # So we need to convert this position to the corresponding speed by adding 1
24        minimum_sufficient_speed = bisect_left(range(1, max_possible_speed), True, key=is_speed_sufficient) + 1
25      
26        # If the speed is equal to the maximum possible speed, it means it wasn't possible to arrive on time
27        # So we return -1; otherwise, return the minimum sufficient speed
28        return -1 if minimum_sufficient_speed == max_possible_speed else minimum_sufficient_speed
29
1class Solution {
2  
3    public int minSpeedOnTime(int[] distances, double hour) {
4        int lowerBound = 1; // Defines the minimum possible speed
5        int upperBound = (int) 1e7; // Defines the maximum possible speed, assuming a constraints' defined upper limit
6      
7        // Binary search to find minimum speed necessary to arrive on time
8        while (lowerBound < upperBound) {
9            int midSpeed = (lowerBound + upperBound) / 2; // Use mid as the candidate speed
10            if (canArriveOnTime(distances, midSpeed, hour)) {
11                upperBound = midSpeed; // If we can arrive on time with this speed, try lower speed
12            } else {
13                lowerBound = midSpeed + 1; // Otherwise, try a higher speed
14            }
15        }
16      
17        // Check if the minimum speed found allows arrival on time
18        return canArriveOnTime(distances, lowerBound, hour) ? lowerBound : -1;
19    }
20
21    // Helper function to check if we can arrive on time given the distances, speed and hour
22    private boolean canArriveOnTime(int[] distances, int speed, double hour) {
23        // Total time taken to travel all distances at the given speed
24        double totalTime = 0.0;
25        for (int i = 0; i < distances.length; ++i) {
26            double segmentTime = (double)distances[i] / speed;
27            // Ceil the time for all segments except the last (no need to wait for a whole hour on the last segment)
28            totalTime += (i == distances.length - 1) ? segmentTime : Math.ceil(segmentTime);
29        }
30        return totalTime <= hour; // Return true if time does not exceed the given hour
31    }
32}
33
1class Solution {
2public:
3    // Function to find the minimum speed needed to arrive on time
4    int minSpeedOnTime(vector<int>& distances, double hour) {
5        // Initialize binary search bounds
6        int minSpeed = 1, maxSpeed = 1e7;
7
8        // Perform binary search to find the minimum feasible speed
9        while (minSpeed < maxSpeed) {
10            int midSpeed = (minSpeed + maxSpeed) >> 1; // Calculate mid speed
11
12            // Check if current speed meets the required time
13            if (canArriveOnTime(distances, midSpeed, hour)) {
14                maxSpeed = midSpeed; // If yes, search in the lower half
15            } else {
16                minSpeed = midSpeed + 1; // If no, search in the upper half
17            }
18        }
19
20        // After binary search, check if the left bound allows to arrive on time
21        return canArriveOnTime(distances, minSpeed, hour) ? minSpeed : -1;
22    }
23
24    // Helper function to check if it is possible to arrive on time at the given speed
25    bool canArriveOnTime(vector<int>& distances, int speed, double hour) {
26        double totalTime = 0; // Variable to store total time taken
27
28        for (int i = 0; i < distances.size(); ++i) {
29            double travelTime = static_cast<double>(distances[i]) / speed;
30          
31            // For all but the last distance, we round up the travel time to the nearest whole number
32            // since you can't travel a fraction of a distance without spending the whole hour
33            totalTime += (i == distances.size() - 1) ? travelTime : ceil(travelTime);
34        }
35      
36        // Return true if the total time does not exceed the given hour, false otherwise
37        return totalTime <= hour;
38    }
39};
40
1/**
2 * Calculate the minimum travel speed required to complete a given set of distances within a specified time.
3 * 
4 * @param {number[]} distances - An array of distances to travel.
5 * @param {number} timeLimit - The time limit to complete all travels.
6 * @return {number} - The minimum speed required to be on time, or -1 if it's impossible.
7 */
8function minSpeedOnTime(distances: number[], timeLimit: number): number {
9    // Check if the travel is possible within the time limit. If there are more distances
10    // than the ceiling value of hours, it's impossible to complete on time.
11    if (distances.length > Math.ceil(timeLimit)) return -1;
12
13    let minSpeed = 1; // Lower bound for binary search (minimum possible speed).
14    let maxSpeed = 10 ** 7; // Upper bound for binary search (arbitrarily high speed).
15
16    while (minSpeed < maxSpeed) {
17        let midSpeed = Math.floor((minSpeed + maxSpeed) / 2);
18        if (arriveOnTime(distances, midSpeed, timeLimit)) {
19            maxSpeed = midSpeed;
20        } else {
21            minSpeed = midSpeed + 1;
22        }
23    }
24
25    // The left boundary of the binary search represents the minimum speed at which we can arrive on time.
26    return minSpeed;
27}
28
29/**
30 * Helper function to check if it's possible to arrive on time at the given speed.
31 * 
32 * @param {number[]} distances - An array of distances to travel.
33 * @param {number} speed - The traveling speed.
34 * @param {number} timeLimit - The time limit to complete all travels.
35 * @return {boolean} - Returns true if it's possible to arrive on time, otherwise false.
36 */
37function arriveOnTime(distances: number[], speed: number, timeLimit: number): boolean {
38    let totalTime = 0.0;
39    let n = distances.length;
40  
41    for (let i = 0; i < n; i++) {
42        let travelTime = distances[i] / speed;
43        // For all but the last distance, round the travel time up to the nearest whole number,
44        // since you can't travel a fraction of the distance at a consistent speed.
45        if (i != n - 1) {
46            travelTime = Math.ceil(travelTime);
47        }
48        totalTime += travelTime;
49    }
50    // Compare the total time taken to travel at the given speed with the time limit.
51    return totalTime <= timeLimit;
52}
53
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

The time complexity of the minSpeedOnTime function is determined by the binary search and the check function that is called at each step of the binary search.

The binary search runs in O(log R), where R is the range of possible speeds, which in this case is 10^7. The +1 correction does not affect the logarithmic complexity.

The check function runs in O(N), where N is the number of elements in the dist list because it needs to iterate over all the distances. Inside the check function, math.ceil function is called which has a constant time O(1). Therefore, for each call of the check function, the time complexity is linear with respect to the number of distances.

Therefore, the overall time complexity of the function is O(N log R) where N is the number of distances in the dist list and R is 10^7.

The space complexity of the function is O(1). No additional space is allocated that grows with the size of the input, except for the variable res, which uses a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫