Skip to main content

Binary Search

Minimum Speed to Arrive on Time Solution in C++/Java/Python/JS

minimum-speed-to-arrive-on-time-problem description
minimum-speed-to-arrive-on-time-problem description

Minimum Speed to Arrive on Time Problem Description:

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the ith train ride.
Each train can only depart at an integer hour, so you may need to wait in between each train ride.
For example, if the 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd train ride at the 2-hour mark. Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.
Tests are generated such that the answer will not exceed 10⁷ and hour will have at most two digits after the decimal point.

Examples:

Input: dist = [1,3,2], hour = 6
Output: 1
Explanation: At speed 1:

  • The first train ride takes 1/1 = 1 hour.
  • Since we are already at an integer hour, we depart immediately at the 1-hour mark. The second train takes 3/1 = 3 hours.
  • Since we are already at an integer hour, we depart immediately at the 4-hour mark. The third train takes 2/1 = 2 hours.
  • You will arrive at exactly the 6-hour mark.

Input: dist = [1,3,2], hour = 2.7
Output: 3
Explanation: At speed 3:

  • The first train ride takes 1/3 = 0.33333 hours.
  • Since we are not at an integer hour, we wait until the 1-hour mark to depart. The second train ride takes 3/3 = 1 hour.
  • Since we are already at an integer hour, we depart immediately at the 2-hour mark. The third train takes 2/3 = 0.66667 hours.
  • You will arrive at the 2.66667-hour mark.

Input: dist = [1,3,2], hour = 1.9
Output: -1
Explanation: It is impossible because the earliest the third train can depart is at the 2-hour mark.

Constraints:

n == dist.length
1 <= n <= 10⁵
1 <= dist[i] <= 10⁵
1 <= hour <= 10⁹
There will be at most two digits after the decimal point in hour.

Brute Force Approach

We are given an array dist where dist[i] represents the distance of the i-th train ride.
We need to find the minimum integer k (speed in km per hour) such that we can reach the office within hour hours under the following conditions:
Each train must travel at speed k, and after each ride, if the arrival time is not an integer hour, we must wait until the next full hour to board the next train.

Let's make some observations:

What is the minimum speed we can travel at?
The smallest speed k must be at least 1 km per hour.
Why?
If k = 0, we will never cover any distance, making it impossible to reach the office. So, the absolute minimum speed must be 1 km per hour.

What is the maximum speed we can travel at?
The maximum speed k should be chosen optimally to ensure minimal time contribution from the last train ride while keeping the answer within the given constraints.

Why should the last train ride contribute the least time?

  • In the given problem, all train rides except the last one are rounded up to the nearest integer hour.
  • However, the last train ride's exact time (dist[n-1] / speed) is added as it is, without rounding.
  • To minimize this additional time, we want the speed to be as large as possible.

Choosing Maximum Speed

  • The problem states that the answer will not exceed 10⁷.
  • To ensure the last train ride contributes the least possible time, we set:
    maxSpeed = 10⁷
  • A speed greater than 10⁷ is unnecessary as it is the highest allowed answer.

Thus, in setting maxSpeed, we choose 10⁷ to minimize the time contribution of the last train ride while ensuring it remains within the problem constraints.

Now that we know the minimum and maximum possible speed values, we need to find the smallest possible speed k such that we can reach the office within hour hours.

It’s clear that k must lie between these two limits:

  • If k is smaller than 1, we won’t make progress in traveling the distances.
  • If k is larger than the longest distance in dist, it’s unnecessary because we can’t travel more than the longest distance in one hour.
  • So, k must be somewhere between 1 and 10⁷.

Now, we can start testing k with the minimum speed (1 km/h) and check all possible values up to the maximum speed (10⁷ km/h).

For each value of k, we check if we can complete all train rides within hour hours. If we find that we can reach the office within hour hours for a certain value of k, we simply return that value of k as the answer.

Why?
Because it will be the smallest speed required to reach the office on time. Any speed k smaller than this would take more than hour hours, making it impossible to arrive on time.

Consider the example with dist = [1, 3, 2] and hour = 2.7 (the amount of time available to reach the office).

We start by taking the minimum speed, which is 1 km/h, as the smallest possible speed, and the maximum speed, which is the largest distance in dist (3 km/h), as the largest possible speed.

We then check how many hours it would take to complete all train rides at each of these speeds:

  • For speed = 1 km/h:
    • The first train takes 1/1 = 1 hour.
    • The second train takes 3/1 = 3 hours, making the total time 4 hours, which is more than 2.7, so it doesn’t work.
  • For speed = 2 km/h:
    • The first train takes 1/2 = 0.5 hours, rounded up to 1 hour (since we must wait for the next integer hour).
    • The second train takes 3/2 = 1.5 hours, rounded up to 2 hours.
    • The third train takes 2/2 = 1 hour.
    • The total time is 4 hours, which is more than 2.7, so it doesn’t work.
  • For speed = 3 km/h:
    • The first train takes 1/3 = 0.3333 hours, rounded up to 1 hour.
    • The second train takes 3/3 = 1 hour.
    • The third train takes 2/3 = 0.6667 hours.
    • The total time is 2.6667 hours, which is within 2.7 hours, so it works.
  • For speed = 4 km/h:
    • The first train takes 1/4 = 0.25 hours, rounded up to 1 hour.
    • The second train takes 3/4 = 0.75 hours, rounded up to 1 hour.
    • The third train takes 2/4 = 0.5 hours.
    • The total time is 2.5 hours, which is within 2.7 hours, so it also works.

Since 3 km/h is the smallest speed where we can reach the office within 2.7 hours, it is the minimum required speed. So, the answer is 3.

Now, consider the monotonic nature of the problem:

  • Any speed between 1 km/h and 2 km/h will not work because the total time exceeds hour = 2.7.
  • However, any speed from 3 km/h onwards will allow us to reach the office on time.
  • Therefore, 3 km/h is the smallest speed that ensures we reach the office within the given time.

Thus, we return 3 as the answer.

Let's call the smallest speed required to reach the office within hour as minSpeed.

Any speed between the minimum possible speed (1 km/h) and minSpeed - 1 km/h won’t work because the total travel time will exceed hour.

However, any speed from minSpeed km/h to the maximum possible speed (the largest distance in dist) will allow us to reach the office on time.

Therefore, minSpeed is the smallest speed at which we can reach the office within the given time, and we return minSpeed as the answer.

minimum-speed-to-arrive-on-time-example

Real-world example: How do you check if you can reach the office within an hour at a specific speed (m)?

Imagine you are commuting to work and must take a series of trains to reach your office. Each train departs only at full hours, so if you arrive at a station mid-hour, you must wait until the next full hour to board the next train.

Now, you want to find the minimum speed (m km/h) that will allow you to reach the office within the given time (hour).

Checking If Speed m is Fast Enough:

You start your journey and set a timer to 0—this timer will track how long your entire commute takes.

For each train ride, you calculate the time required at speed m:

  • You divide the distance of the train ride by m, which gives the exact travel time.
  • Since trains can only depart at integer hours, if the result is a fraction, you must wait until the next full hour before catching the next train. This is handled using the ceil function.
  • You add this waiting time to your total travel time.

When you reach the final train ride, there’s no need to wait anymore—you simply add the exact travel time to the total.

Did You Reach on Time?

  • If the total time is less than or equal to hour, then speed m is fast enough, and you will arrive on time.
  • Otherwise, this speed is too slow, and you won’t make it in time.

By testing different values of m, you can find the minimum speed that allows you to reach the office on time!

💡
Try it Yourself!

Let's understand with an example:

Minimum Speed to Arrive on Time Example:

Input:

  • dist = [1,3,2]
  • hour = 2.7

Step 1: Initialize Search Range

  • Set low = 1 (minimum possible speed).
  • Set high = 10⁷ (maximum possible speed).
  • Start checking speeds from low = 1 and incrementally increase until we find a valid speed.

Step 2: Checking Each Speed One by One

  • Speed = 1
    • First train takes ceil(1/1) = 1 hour.
    • Second train takes ceil(3/1) = 3 hours.
    • Third train takes 2/1 = 2 hours.
    • Total time = 1 + 3 + 2 = 6 (exceeds 2.7 hours).
    • Not valid, try next speed.
  • Speed = 2
    • First train takes ceil(1/2) = 1 hour.
    • Second train takes ceil(3/2) = 2 hours.
    • Third train takes 2/2 = 1 hour.
    • Total time = 1 + 2 + 1 = 4 (exceeds 2.7 hours).
    • Not valid, try next speed.
  • Speed = 3
    • First train takes ceil(1/3) = 1 hour.
    • Second train takes ceil(3/3) = 1 hour.
    • Third train takes 2/3 = 0.6667 hour.
    • Total time = 1 + 1 + 0.6667 = 2.6667 (≤ 2.7 hours).
    • Valid speed found: 3.

Step 3: Return Result

  • The minimum speed required to reach on time is 3.

Steps to Implement the Solution:

Minimum Speed to Arrive on Time Example:

Helper Function (isPossible)
Purpose: Check if it is possible to reach the office within the given time at a specified speed.

Steps:

  1. Initialize total travel time to 0.
  2. Iterate through all train rides except the last one:
    Compute the time taken for each train ride and round it up to the next whole hour.
  3. For the last train ride:
    Compute the exact travel time without rounding up.
  4. Return true if the total travel time is within the allowed limit (hour), otherwise return false.

Main Function (minSpeedOnTime)
Purpose: Find the minimum speed required to reach the office on time by iterating over all possible speeds.

Steps:

  1. Initialize the search range:
    low = 1 (minimum possible speed).
    high = 10⁷ (maximum possible speed).
    minSpeed = -1 (store the minimum valid speed).
  2. Iterate over all possible speeds from low to high:
    If isPossible(speed) is true:
    Store the first valid speed found.
    Break the loop, as we are searching for the smallest valid speed.
  3. Return the minimum speed found or -1 if reaching on time is impossible.

Minimum Speed to Arrive on Time Leetcode Solution

Code Implementation / Leetcode solutions of Minimum Speed to Arrive on Time
1. Minimum Speed to Arrive on Time C++ Solution Try on Compiler 
class Solution {
    // Function to check if it is possible to reach the office within given hour at speed 'm'
    bool isPossible(vector<int> &dist, double hour, long long m) {

        // Initialize time counter to 0
        double time = 0;
        
        // Iterate through all train rides except the last one
        for(int i = 0; i < dist.size() - 1; i++) {

            // Compute time taken for the current train ride and round it up to the next integer hour
            time += ceil(dist[i] * 1.0 / m);
        }
        
        // Add exact time for the last train ride (no need to round up)
        time += (dist[dist.size() - 1] * 1.0 / m);
        
        // Check if the total travel time is within the allowed hour
        return time <= hour;
    }

public:
    // Function to find the minimum speed required to reach on time
    int minSpeedOnTime(vector<int>& dist, double hour) {

        // Define the lower and upper bounds of speed
        long long low = 1, high = 1e7;
        
        // Variable to store the minimum valid speed
        long long minSpeed = -1;

        // Iterate through all possible speeds from low to high
        for(int i = low; i <= high; i++) {

            // Check if the current speed is sufficient to reach on time
            if(isPossible(dist, hour, i)) {
                
                // Store the minimum speed found and break out of the loop
                minSpeed = i;
                break;
            }
        }

        // Return the minimum valid speed as an integer
        return (int)minSpeed;
    }
};

2. Minimum Speed to Arrive on Time Java Solution Try on Compiler 
class Solution {
    // Function to check if it is possible to reach the office within given hour at speed 'm'
    private boolean isPossible(int[] dist, double hour, long m) {

        // Initialize time counter to 0
        double time = 0;
        
        // Iterate through all train rides except the last one
        for (int i = 0; i < dist.length - 1; i++) {

            // Compute time taken for the current train ride and round it up to the next integer hour
            time += Math.ceil((double) dist[i] / m);
        }
        
        // Add exact time for the last train ride (no need to round up)
        time += (double) dist[dist.length - 1] / m;
        
        // Check if the total travel time is within the allowed hour
        return time <= hour;
    }

    // Function to find the minimum speed required to reach on time
    public int minSpeedOnTime(int[] dist, double hour) {

        // Define the lower and upper bounds of speed
        long low = 1, high = (long) 1e7;
        
        // Variable to store the minimum valid speed
        long minSpeed = -1;

        // Iterate through all possible speeds from low to high
        for (long i = low; i <= high; i++) {

            // Check if the current speed is sufficient to reach on time
            if (isPossible(dist, hour, i)) {
                
                // Store the minimum speed found and break out of the loop
                minSpeed = i;
                break;
            }
        }

        // Return the minimum valid speed as an integer
        return (int) minSpeed;
    }
}

3. Minimum Speed to Arrive on Time Python Solution Try on Compiler 
import math

class Solution:
    # Function to check if it is possible to reach the office within given hour at speed 'm'
    def isPossible(self, dist, hour, m):

        # Initialize time counter to 0
        time = 0.0
        
        # Iterate through all train rides except the last one
        for i in range(len(dist) - 1):

            # Compute time taken for the current train ride and round it up to the next integer hour
            time += (dist[i] + m - 1 ) / m
        
        # Add exact time for the last train ride (no need to round up)
        time += (dist[-1] * 1.0 / m)
        
        # Check if the total travel time is within the allowed hour
        return time <= hour

    # Function to find the minimum speed required to reach on time
    def minSpeedOnTime(self, dist, hour):

        # Define the lower and upper bounds of speed
        low, high = 1, int(1e7)
        
        # Variable to store the minimum valid speed
        minSpeed = -1

        # Iterate through all possible speeds from low to high
        for i in range(low, high + 1):
            
            # Check if the current speed is sufficient to reach on time
            if self.isPossible(dist, hour, i):

                # Store the minimum speed found and break out of the loop
                minSpeed = i
                break
        
        # Return the minimum valid speed
        return minSpeed

4. Minimum Speed to Arrive on Time Javascript Solution Try on Compiler 
/**
 * @param {number[]} dist
 * @param {number} hour
 * @return {number}
 */
// Function to check if it is possible to reach the office within given hour at speed 'm'
var isPossible = function (dist, hour, m) {

    // Initialize time counter to 0
    let time = 0;

    // Iterate through all train rides except the last one
    for (let i = 0; i < dist.length - 1; i++) {

        // Compute time taken for the current train ride and round it up to the next integer hour
        time += Math.ceil(dist[i] / m);
    }

    // Add exact time for the last train ride (no need to round up)
    time += dist[dist.length - 1] / m;

    // Check if the total travel time is within the allowed hour
    return time <= hour;
}
var minSpeedOnTime = function (dist, hour) {

    // Define the lower and upper bounds of speed
    let low = 1, high = 1e7;

    // Variable to store the minimum valid speed
    let minSpeed = -1;

    // Iterate through all possible speeds from low to high
    for (let i = low; i <= high; i++) {

        // Check if the current speed is sufficient to reach on time
        if (isPossible(dist, hour, i)) {

            // Store the minimum speed found and break out of the loop
            minSpeed = i;
            break;
        }
    }

    // Return the minimum valid speed
    return minSpeed;
};

Minimum Speed to Arrive on Time Complexity Analysis

Time Complexity: O(n × maxSpeed)

For Each Speed (Loop from minSpeed to maxSpeed):
In the worst case, this loop runs O(maxSpeed) = O(10⁷) times.
We iterate over every possible speed from minSpeed = 1 to maxSpeed = 10⁷ (worst case).

For Each Distance (Inside the isPossible Function):
For each speed, we check if it allows reaching the destination within hour.
This requires iterating over the dist array once, which takes O(n) time, where n is the number of distances.

Combining Both:

  • The outer loop runs O(maxSpeed) times.
  • The inner isPossible function runs in O(n) for each speed.

Final Time Complexity: O(n × maxSpeed)

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    The extra space used for variables like time, is constant. These are just primitive variables that occupy O(1) space.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(n)
    The input consists of the dist array, which is the main data structure, and its size is O(n) where n is the number of piles.
    Therefore, the total space complexity is O(n).

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O(n × maxSpeed), where, n is the number of elements in the dist array (with an upper limit of 10⁵). maxSpeed represents the highest possible speed, which can be as large as 10⁷ in the worst case. This means the worst-case scenario requires up to O(10⁵ × 10⁷) = O(10¹²) operations.

Given that competitive programming problems typically allow around 10⁶ to 10⁸ operations per test case, this approach is inefficient for the worst-case inputs.

While the solution may run within a reasonable time for small or average inputs, large constraints (such as n = 10⁵ and hour = 10⁹) will push it beyond practical execution limits. The inefficiency arises due to checking every possible speed from 1 to maxSpeed, making the approach too slow for large inputs.

Hence, the final Time Complexity of O(n × maxSpeed), will be inefficient for large constraints.

How to optimize it?

In the previous approach, we examined the minimum and maximum speeds at which the trains could travel and checked every speed within that range to find the minimum speed s such that all trains could reach the office within hour time. This resulted in a time complexity of O(n * maxSpeed), which was too slow and caused a TLE (Time Limit Exceeded) error.

Now, let’s think about improving this.
The main issue was that we checked every speed from minimum to maximum, which took a lot of time.

Can we make this part faster?

Yes! Here’s the hint:

We are searching for the minimum speed such that all the trains reach the office within hour time, and we know that this speed lies between the minimum speed (1 km/h) and the maximum speed (the largest distance in dist).

Now that we know the two endpoints, the minimum possible speed and the maximum possible speed, let's make a few observations:

  1. The search space is sorted:
    The range of speeds, from the minimum speed (1) to the maximum speed (the largest distance in dist), is naturally sorted.
  2. The search space is monotonic:
  • If a certain speed s allows all trains to reach the office within hour time, then any larger speed will also work.
  • If a certain speed s does not allow the trains to reach on time, then any smaller speed will also fail.
  • For example, consider dist = [1,3,2] and hour = 2.7.
    If we check speed s = 2 km/h, the trains will arrive late (False).
    If we check speed s = 3 km/h, the trains will arrive on time (True).
    For all speeds ≥ 3 km/h, the trains will always arrive on time (T, T, T, T…).

    This illustrates the monotonic property: Once a speed works (s = 3 km/h), all higher speeds will also work.
  1. The middle element helps minimize or maximize the search space:
    If we take the middle value of the current range and check if the trains can reach the office within hour time, we can narrow the search space:
    If it works, we move to the left half to find a smaller valid speed.
    If it doesn’t work, we move to the right half to find a larger speed that works.

If we plot a graph with the range of speeds on the x-axis and whether the trains reach the office on time on the y-axis, we can observe the following:

  • Before the minimum valid speed (minSpeed), the trains cannot reach the office on time.
  • From minSpeed onwards, the trains can reach the office within hour time.
  • Since we are looking for the smallest speed that allows the trains to reach the office on time, minSpeed is our answer.
minimum-speed-to-arrive-on-time-graph

With these points in mind, it's clear that instead of checking all values from the minimum to the maximum speed, we can take the middle value and continually reduce the search space using binary search.

Does this approach remind you of something you've seen before?

Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the speed range, we efficiently narrow down the search space to find the minimum speed that allows Koko to finish all the bananas within h hours, instead of checking each value linearly.

💡
How binary search works?

Minimum Speed to Arrive on Time Binary Search Algorithm

Binary search can help us quickly find the minimum speed by narrowing down the range in each step.

We can use binary search to determine the minimum speed at which all the trains must travel to reach the office within hour time.

  1. Initialize the search range with low as the minimum possible speed (1) and high as the maximum possible speed (1e7).
  2. Take the middle value between low and high as the potential speed.
    • If this mid-value allows you to reach the office on time, we store it as a potential answer and continue searching in the left half to find a smaller valid speed.
    • Otherwise, if you fail to reach the office on time, we move the search to the right half to find a larger valid speed.
  3. Repeat the process until low > high. The stored answer is returned as the minimum speed needed to reach the office on time.

Once the condition breaks, the stored answer is returned as the minimum speed.

By using binary search, we can cut the search space in half at each step, which makes the solution much faster and avoids the TLE issue.

Let us understand this with a video,

0:00
/2:06

minimum-speed-to-arrive-on-time-optimal approach animation explaination

💡
Try it Yourself!

Let's understand with an example:

Minimum Speed to Arrive on Time Example:

Input: dist = [1,3,2], hour = 2.7

  1. Initialize Search Range:
    • low = 1, high = 1e7
  3. Binary Search Iterations:
    • Iteration 1:
      • mid = (1 + 1e7) / 2 = 5000000
      • Check if speed 5000000 allows arrival within 2.7 hours.
      • Update high = 5000000, store minSpeed = 5000000.
    • Iteration 2:
      • mid = (1 + 5000000) / 2 = 2500000
      • Check if speed 2500000 allows arrival within 2.7 hours.
      • Update high = 2500000, store minSpeed = 2500000.
    • Repeat narrowing down the range until low = high.
    • Final Iteration:
      • mid = 3
      • Check if speed 3 allows arrival within 2.7 hours.
      • Update high = 3, store minSpeed = 3.
  5. Result: minSpeed = 3

How to code it up:

Helper Function (isPossible)
Purpose: Check if it is possible to reach the office within the given time at a specified speed.

Steps:

  1. Initialize total travel time to 0.
  2. Iterate through all train rides except the last one:
    • Compute the time for each train ride and round it up to the next whole hour.
  4. For the last train ride:
    • Compute the exact travel time without rounding up.
  6. Return true if the total travel time is within the given limit (hour), otherwise return false.

Main Function (minSpeedOnTime)
Purpose: Find the minimum speed required to reach the office on time using binary search.

Steps:

  1. Initialize the search range:
    • low = 1 (minimum possible speed).
    • high = 10⁷ (maximum possible speed).
    • minSpeed = -1 (store the minimum valid speed).
  3. Perform binary search:
    • While low ≤ high:
      • Compute mid-speed as the middle of the current range.
      • If isPossible(mid-speed) is true:
        • Store mid-speed as a potential answer.
        • Search for a lower valid speed by updating high = mid - 1.
      • Otherwise, increase low = mid + 1 to check for a higher valid speed.
  5. Return the minimum speed found or -1 if reaching on time is impossible.

that Leetcode Solution

Code Implementation / Leetcode solutions of Minimum Speed to Arrive on Time
1. Minimum Speed to Arrive on Time C++ Solution Try on Compiler 
class Solution {
    // Function to check if it is possible to reach the office within the given time at speed 'm'
    bool isPossible(vector<int> &dist, double hour, long long m) {
        
        // Initialize total travel time to 0
        double time = 0;
        
        // Iterate over all train rides except the last one
        for(int i = 0; i < dist.size() - 1; i++) {
            
            // Calculate the time taken for each train ride and round it up
            time += ceil(dist[i] * 1.0 / m);
        }
        
        // For the last train ride, take the exact division result
        time += (dist[dist.size() - 1] * 1.0 / m);
        
        // Return true if the total travel time is within the given hour, else false
        return time <= hour;
    }

public:
    // Function to find the minimum speed required to reach the office on time
    int minSpeedOnTime(vector<int>& dist, double hour) {
        
        // Initialize the search range for speed
        long long low = 1, high = 1e7;
        
        // Variable to store the minimum valid speed
        long long minSpeed = -1;

        // Apply binary search
        while (low <= high) {
            
            // Calculate the mid-speed
            long long mid = low - (low - high) / 2;
            
            // Check if mid-speed allows reaching the office on time
            if (isPossible(dist, hour, mid)) {
                
                // Store mid as a potential answer
                minSpeed = mid;
                
                // Try to find a lower valid speed
                high = mid - 1;
            } else {
                
                // Increase the lower bound to search for a higher valid speed
                low = mid + 1;
            }
        }

        // Return the minimum speed found or -1 if not possible
        return (int)minSpeed;
    }
};

2. Minimum Speed to Arrive on Time Java Solution Try on Compiler 
class Solution {
    // Function to check if it is possible to reach the office within the given time at speed 'm'
    private boolean isPossible(int[] dist, double hour, long m) {
        
        // Initialize total travel time to 0
        double time = 0;
        
        // Iterate over all train rides except the last one
        for (int i = 0; i < dist.length - 1; i++) {
            
            // Calculate the time taken for each train ride and round it up
            time += Math.ceil((double) dist[i] / m);
        }
        
        // For the last train ride, take the exact division result
        time += (double) dist[dist.length - 1] / m;
        
        // Return true if the total travel time is within the given hour, else false
        return time <= hour;
    }

    // Function to find the minimum speed required to reach the office on time
    public int minSpeedOnTime(int[] dist, double hour) {
        
        // Initialize the search range for speed
        long low = 1, high = (long) 1e7;
        
        // Variable to store the minimum valid speed
        long minSpeed = -1;

        // Apply binary search
        while (low <= high) {
            
            // Calculate the mid-speed
            long mid = low + (high - low) / 2;
            
            // Check if mid-speed allows reaching the office on time
            if (isPossible(dist, hour, mid)) {
                
                // Store mid as a potential answer
                minSpeed = mid;
                
                // Try to find a lower valid speed
                high = mid - 1;
            } else {
                
                // Increase the lower bound to search for a higher valid speed
                low = mid + 1;
            }
        }

        // Return the minimum speed found or -1 if not possible
        return (int) minSpeed;
    }
}

3. Minimum Speed to Arrive on Time Python Solution Try on Compiler 
import math

class Solution:
    # Function to check if it is possible to reach the office within the given time at speed 'm'
    def isPossible(self, dist, hour, m):
        
        # Initialize total travel time to 0
        time = 0
        
        # Iterate over all train rides except the last one
        for i in range(len(dist) - 1):
            
            # Calculate the time taken for each train ride and round it up
            time += (dist[i] + m - 1 ) / m
        
        # For the last train ride, take the exact division result
        time += (dist[-1] * 1.0) / m
        
        # Return true if the total travel time is within the given hour, else false
        return time <= hour

    # Function to find the minimum speed required to reach the office on time
    def minSpeedOnTime(self, dist, hour):
        
        # Initialize the search range for speed
        low, high = 1, int(1e7)
        
        # Variable to store the minimum valid speed
        minSpeed = -1

        # Apply binary search
        while low <= high:
            
            # Calculate the mid-speed
            mid = low + (high - low) // 2
            
            # Check if mid-speed allows reaching the office on time
            if self.isPossible(dist, hour, mid):
                
                # Store mid as a potential answer
                minSpeed = mid
                
                # Try to find a lower valid speed
                high = mid - 1
            else:
                
                # Increase the lower bound to search for a higher valid speed
                low = mid + 1

        # Return the minimum speed found or -1 if not possible
        return minSpeed

4. Minimum Speed to Arrive on Time Javascript Solution Try on Compiler 
/**
 * @param {number[]} dist
 * @param {number} hour
 * @return {number}
 */
// Function to check if it is possible to reach the office within given hour at speed 'm'
var isPossible = function (dist, hour, m) {

    // Initialize time counter to 0
    let time = 0;

    // Iterate through all train rides except the last one
    for (let i = 0; i < dist.length - 1; i++) {

        // Compute time taken for the current train ride and round it up to the next integer hour
        time += Math.ceil(dist[i] / m);
    }

    // Add exact time for the last train ride (no need to round up)
    time += dist[dist.length - 1] / m;

    // Check if the total travel time is within the allowed hour
    return time <= hour;
}
var minSpeedOnTime = function (dist, hour) {

    // Initialize the search range for speed
        let low = 1, high = 1e7;
        
        // Variable to store the minimum valid speed
        let minSpeed = -1;

        // Apply binary search
        while (low <= high) {
            
            // Calculate the mid-speed
            let mid = Math.floor(low + (high - low) / 2);
            
            // Check if mid-speed allows reaching the office on time
            if (isPossible(dist, hour, mid)) {
                
                // Store mid as a potential answer
                minSpeed = mid;
                
                // Try to find a lower valid speed
                high = mid - 1;
            } else {
                
                // Increase the lower bound to search for a higher valid speed
                low = mid + 1;
            }
        }

        // Return the minimum speed found or -1 if not possible
        return minSpeed;
};

Minimum Speed to Arrive on Time Complexity Analysis

Time Complexity: O(n)

The problem is solved using binary search, which efficiently finds the minimum speed required to reach the office on time.

Step 1: Understanding the Search Space

  • The possible values of speed range from 1 to 10⁷ (as per constraints).
  • Instead of checking all values linearly (which would be slow), we apply binary search.

Step 2: Binary Search Complexity

  • Binary search reduces the search space by half in each iteration.
  • The number of iterations required to search from 1 to 10⁷ is O(log 10⁷) ≈ O(24).

Step 3: Checking if a Speed is Valid

  • For each binary search iteration, we call the isPossible function to check if the given speed allows reaching on time.
  • Inside isPossible, we iterate through the dist array (size n) to compute the total time required.
  • This takes O(n) time per binary search iteration.

Final Complexity Calculation

  • Binary Search: O(log maxSpeed) = O(log 10⁷) ≈ O(24)
  • Time Calculation (isPossible function): O(n)
  • Total Complexity = O(n * log maxSpeed)
    → O(n * log 10⁷) ≈ O(n * 24) ≈ O(n) in practical scenarios.

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    The extra space used for variables like time, is constant. These are just primitive variables that occupy O(1) space.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(n)
    The input consists of the dist array, which is the main data structure, and its size is O(n) where n is the number of piles.
    Therefore, the total space complexity is O(n).

Similar Problems

The Minimum Speed to Arrive on Time and Minimum Platforms problems on LeetCode are classic examples of efficient scheduling and optimization challenges. The Minimum Speed to Arrive on Time problem often requires techniques like binary search to determine the optimal speed for timely arrival. Meanwhile, the Minimum Platforms problem involves strategies such as sorting and greedy algorithms to efficiently manage train arrival and departure timings. Understanding these problems helps improve algorithmic thinking and enhances your ability to tackle real-world scheduling scenarios.

Now that we have successfully tackled this problem, let's try similar problems.

1. Maximum Candies Allocated to K Children

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

2. Minimum Skips to Arrive at Meeting On Time

You are given an integer hoursBefore, the number of hours you have to travel to your meeting. To arrive at your meeting, you have to travel through n roads. The road lengths are given as an integer array dist of length n, where dist[i] describes the length of the ith road in kilometers. In addition, you are given an integer speed, which is the speed (in km/h) you will travel at.

After you travel road i, you must rest and wait for the next integer hour before you can begin traveling on the next road. Note that you do not have to rest after traveling the last road because you are already at the meeting.

  • For example, if traveling a road takes 1.4 hours, you must wait until the 2 hour mark before traveling the next road. If traveling a road takes exactly 2 hours, you do not need to wait.

However, you are allowed to skip some rests to be able to arrive on time, meaning you do not need to wait for the next integer hour. Note that this means you may finish traveling future roads at different hour marks.

  • For example, suppose traveling the first road takes 1.4 hours and traveling the second road takes 0.6 hours. Skipping the rest after the first road will mean you finish traveling the second road right at the 2 hour mark, letting you start traveling the third road immediately.

Return the minimum number of skips required to arrive at the meeting on time, or -1 if it is impossible.

3. Minimum Time to Complete Trips

You are given an array time where time[i] denotes the time taken by the ith 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.

4. The Latest Time to Catch a Bus

You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the ith bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the jth passenger. All bus departure times are unique. All passenger arrival times are unique.

You are given an integer capacity, which represents the maximum number of passengers that can get on each bus.

When a passenger arrives, they will wait in line for the next available bus. You can get on a bus that departs at x minutes if you arrive at y minutes where y <= x, and the bus is not full. Passengers with the earliest arrival times get on the bus first.

More formally when a bus arrives, either:

  • If capacity or fewer passengers are waiting for a bus, they will all get on the bus, or
  • The capacity passengers with the earliest arrival times will get on the bus.

Return the latest time you may arrive at the bus station to catch a bus. You cannot arrive at the same time as another passenger.

Note: The arrays buses and passengers are not necessarily sorted.

5. Minimize Maximum of Array

You are given a 0-indexed array nums comprising of n non-negative integers.

In one operation, you must:

  • Choose an integer i such that 1 <= i < n and nums[i] > 0.
  • Decrease nums[i] by 1.
  • Increase nums[i - 1] by 1.

Return the minimum possible value of the maximum integer of nums after performing any number of operations.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8