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.
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.length1 <= n <= 1051 <= dist[i] <= 1051 <= hour <= 109hour.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).
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:
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.
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.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Kotlin
| Approach | Complexity |
|---|---|
| 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). |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Speed Simulation | O(n * m) | O(1) | Useful for understanding the travel time calculation and constraints before optimization |
| Binary Search on Speed | O(n log m) | O(1) | Best choice when the answer lies in a numeric range and feasibility is monotonic |
Minimum Speed to Arrive on Time | Binary Search | INTUITION | Online Assessment | Leetcode-1870 • codestorywithMIK • 7,554 views views
Watch 9 more video solutions →Practice Minimum Speed to Arrive on Time with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor