Skip to main content
Talentd

Minimum Speed to Arrive on Time - Solution & Explanation

MediumArrayBinary Search28 min readAsked at: Apple, Google
Practice this problem

Problem Statement

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 107 and hour will have at most two digits after the decimal point.

 

Example 1:

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.

Example 2:

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.

Example 3:

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 <= 105
  • 1 <= dist[i] <= 105
  • 1 <= hour <= 109
  • There will be at most two digits after the decimal point in hour.

Approach Overview

Problem Overview: You are given an array dist where each value represents the distance of a train ride. Trains must depart at integer hours except the last ride. The task is to find the minimum integer speed required to finish all rides within a given time limit hour. If it is impossible, return -1.

Approach 1: Brute Force Speed Simulation (O(n * m) time, O(1) space)

The most direct idea is to test every possible speed starting from 1 and simulate the total travel time. For each speed, iterate through dist and compute time as ceil(dist[i] / speed) for every segment except the last one, which uses exact division. If the total time is less than or equal to hour, that speed works. Continue increasing the speed until you find the smallest valid one. The problem is the upper bound for speed can be very large (up to millions), making this approach inefficient with O(n * m) time where m is the maximum tested speed.

Approach 2: Binary Search on Speed (O(n log m) time, O(1) space)

The key observation is monotonic behavior: if a certain speed allows you to arrive on time, any higher speed will also work. This makes the answer searchable using binary search. Define a search range for speed from 1 to a large upper bound (commonly 10^7). For each candidate speed, iterate through the array and compute the total travel time. Use ceil(dist[i] / speed) for all rides except the last, because you must wait for the next integer departure time. The last ride uses the exact fractional time.

If the computed time is within hour, the speed is valid, so try a smaller value by moving the right boundary. Otherwise, increase the speed by moving the left boundary. Continue until the smallest feasible speed is found. Each feasibility check scans the array once, giving O(n) per iteration, and the binary search over the speed range contributes a log m factor.

This pattern—searching over an answer range and validating with a function—is a classic binary search on answer technique frequently used in scheduling and optimization problems.

Recommended for interviews: The binary search approach is what interviewers expect. A brute force explanation shows you understand the simulation logic and the departure constraint, but recognizing the monotonic property and applying binary search demonstrates stronger algorithmic thinking and reduces the complexity to O(n log m).

Approach 1: Binary Search Approach

Idea: To find the minimum positive integer speed that allows you to reach the office in the given time, you can use binary search on the speed. Initialize the left boundary to 1 (minimum speed) and right boundary to a large number (e.g., 10^7, as specified in the problem statement), then narrow down the possible speed by simulating the commute.

Steps:

  • Perform binary search on speed from 1 to 10^7.
  • For each candidate speed, iterate over all trains, compute the total time taken, rounding up the time taken for all but the last train.
  • If total time is less than or equal to given hour, try with a smaller speed. Otherwise, try with a larger speed.

If you narrow down to a result, it is the minimum speed required. If search is exhausted without finding a valid speed, return -1.

The solution involves performing a binary search over possible speeds. The minSpeedOnTime function iterates over each train's distance at a given mid speed, calculating the time taken accounting for waiting until the next hour if necessary. The result is a narrowed-down speed that allows for reaching within the specified hour, making use of ceiling round-ups for all train rides except for the last one.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log k), where n is the number of train distances and k is the maximum speed (10^7).
Space Complexity: O(1), as the solution does not require any extra space beyond a fixed set of variables.

Try this approach in the editor →

Approach 2: Binary Search

We notice that if a speed value v allows us to arrive within the stipulated time, then for any v' > v, we can also definitely arrive within the stipulated time. This exhibits monotonicity, hence we can use binary search to find the smallest speed value that meets the condition.

Before conducting the binary search, we need to first determine if it is possible to arrive within the stipulated time. If the number of trains is greater than the ceiling of the stipulated time, then it is definitely impossible to arrive within the stipulated time, and we should directly return -1.

Next, we define the left and right boundaries for the binary search as l = 1, r = 10^7 + 1, and then we take the middle value mid = \frac{l + r}{2} each time to check if it meets the condition. If it does, we move the right boundary to mid; otherwise, we move the left boundary to mid + 1.

The problem is transformed into determining whether a speed value v can allow us to arrive within the stipulated time. We can traverse each train trip, calculate the running time of each trip t = \frac{d}{v}, if it is the last trip, we directly add t; otherwise, we round up and add t. Finally, we check if the total time is less than or equal to the stipulated time, if so, it means the condition is met.

After the binary search ends, if the left boundary exceeds 10^7, it means we cannot arrive within the stipulated time, and we return -1; otherwise, we return the left boundary.

The time complexity is O(n times log M), where n and M are the number of train trips and the upper bound of the speed, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptKotlin

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Kotlin

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search Approach

Time Complexity: O(n log k), where n is the number of train distances and k is the maximum speed (10^7).
Space Complexity: O(1), as the solution does not require any extra space beyond a fixed set of variables.

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Speed SimulationO(n * m)O(1)Useful for understanding the travel time calculation and constraints before optimization
Binary Search on SpeedO(n log m)O(1)Best choice when the answer lies in a numeric range and feasibility is monotonic

Video Solution

Minimum Speed to Arrive on Time | Binary Search | INTUITION | Online Assessment | Leetcode-1870 • codestorywithMIK • 8,527 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Speed to Arrive on Time easy or hard?
Minimum Speed to Arrive on Time is rated Medium difficulty on LeetCode. The challenge lies in recognizing the monotonic relationship between speed and total travel time and applying binary search on the answer rather than directly iterating over speeds.
Minimum Speed to Arrive on Time Python or Java solution?
Implement binary search on speed and a helper function that computes total travel time for a given speed. The logic is identical across Python, Java, C++, C#, and JavaScript—iterate through the array, apply ceiling division for intermediate segments, and adjust the search range based on feasibility.
How to solve Minimum Speed to Arrive on Time in O(n log m)?
Use binary search on the possible speed range. For each candidate speed, iterate through the distances and compute total travel time using ceil(dist[i] / speed) for all segments except the last one. If the computed time is within the allowed hour, move the search left to find a smaller valid speed.
What is the best approach for Minimum Speed to Arrive on Time?
Binary search on the speed range is the most efficient approach. The idea is that if a certain speed allows arriving within the given hour, any higher speed will also work. This monotonic property allows binary search over possible speeds while checking feasibility in O(n) time, resulting in O(n log m) total complexity.
Is Minimum Speed to Arrive on Time asked at Google/Amazon/Meta?
Binary search optimization problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests understanding of monotonic conditions, search space reduction, and efficient feasibility checks.
What data structure is used in Minimum Speed to Arrive on Time?
The problem primarily uses arrays to store distances and applies binary search over a numeric range of speeds. No complex data structures are required; the key technique is binary search combined with arithmetic calculations for travel time.
What is the time complexity of Minimum Speed to Arrive on Time?
The optimal solution runs in O(n log m) time where n is the number of train rides and m is the maximum possible speed bound. Each binary search step evaluates total travel time by scanning the array once. Space complexity remains O(1) since only a few variables are used.

Ready to solve this problem?

Practice Minimum Speed to Arrive on Time with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Candies Allocated to K Children

Next

Minimize Maximum of Array