Watch 10 video solutions for Minimum Speed to Arrive on Time, a medium level problem involving Array, Binary Search. This walkthrough by codestorywithMIK has 7,554 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
| 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 |