Minimum Speed to Arrive on Time
MedPrompt
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
1sttrain ride takes1.5hours, you must wait for an additional0.5hours before you can depart on the2ndtrain 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 <= 109- There will be at most two digits after the decimal point in
hour.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a linear scan through all possible speeds. Starting from a speed of 1, we check each integer speed one by one. For every speed, we calculate the total time it would take to travel all the distances, considering the waiting time between trains. The first speed that results in a total time less than or equal to the allowed hour is the minimum speed we are looking for. If we exhaust all possible speeds up to a given limit without finding a solution, we conclude it's impossible.
Algorithm
- Iterate through all possible integer speeds
sstarting from 1 up to a reasonable upper bound (e.g.,10^7, as suggested by the problem constraints). - For each speed
s, create a helper function to calculate the total time required to complete all journeys. - Inside the helper function:
- Initialize
totalTime = 0.0. - For the first
n-1train rides, calculate the time asdist[i] / s. Since you must wait until the next integer hour, addceil(dist[i] / s)tototalTime. - For the last train ride, no waiting is needed, so simply add
dist[n-1] / stototalTime.
- Initialize
- If the calculated
totalTimeis less than or equal to the givenhour, thensis the minimum possible speed. Returnsimmediately. - If the loop completes without finding any valid speed, it means it's impossible to arrive on time. Return -1.
Walkthrough
The core of this method is a helper function, calculateTime(dist, speed), which computes the total travel time for a given speed. This function iterates through the dist array. For the first n-1 trains, the time taken is dist[i] / speed, and since we must wait for the next integer hour, we take the ceiling of this value. For the last train, we simply add dist[n-1] / speed as no further waiting is required.
The main function then calls this helper in a loop, starting speed from 1. If calculateTime returns a total time less than or equal to hour, we've found our answer. The problem statement guarantees that the answer will not exceed 10^7, so we can use this as our search limit. If the loop completes without finding a suitable speed, we return -1.
class Solution { public int minSpeedOnTime(int[] dist, double hour) { // The problem states the answer will not exceed 10^7. int maxSpeed = 10000000; for (int speed = 1; speed <= maxSpeed; speed++) { if (calculateTime(dist, speed) <= hour) { return speed; } } return -1; } private double calculateTime(int[] dist, int speed) { double totalTime = 0.0; for (int i = 0; i < dist.length - 1; i++) { totalTime += Math.ceil((double) dist[i] / speed); } totalTime += (double) dist[dist.length - 1] / speed; return totalTime; }}Complexity
Time
O(K * N), where `N` is the number of trains (`dist.length`) and `K` is the maximum speed to check (up to 10^7). This is too slow for the given constraints.
Space
O(1), as we only use a few variables to store the current state.
Trade-offs
Pros
Simple to understand and implement.
Correctly finds the minimum speed if one exists within the searched range.
Cons
Extremely inefficient due to the large search space for speed.
Will result in a 'Time Limit Exceeded' (TLE) error for larger constraints.
A more efficient approach is to use binary search on the answer (the speed). The key observation is that if a certain speed s allows you to arrive on time, any speed greater than s will also work. This monotonic property (as speed increases, time decreases) makes the problem suitable for binary search. We can search for the minimum valid speed in a range from 1 to a reasonable maximum (like 10^7). For each candidate speed, we check if it's possible to arrive on time. Based on the result, we eliminate half of the search space, drastically reducing the number of checks needed compared to the brute-force method.
Algorithm
- Recognize that the total travel time is a non-increasing function of speed. This monotonicity allows for binary search.
- Define a search range for the speed. The lower bound
lowis 1, and the upper boundhighcan be set to10^7(as per the problem's hint) or a slightly larger safe number. - Initialize the answer
minSpeed = -1. - While
low <= high:- Calculate the middle speed
mid = low + (high - low) / 2. - Use a helper function to calculate the total time required for speed
mid. - If the calculated time is less than or equal to
hour:midis a potential answer. Store it:minSpeed = mid.- Try to find an even smaller speed by searching in the lower half:
high = mid - 1.
- Otherwise (if the time is greater than
hour):midis too slow. Search for a faster speed in the upper half:low = mid + 1.
- Calculate the middle speed
- After the loop,
minSpeedwill hold the minimum valid speed found, or -1 if none was found.
Walkthrough
We define a search space for the speed, from a lower bound of 1 to an upper bound of 10^7. We then perform a binary search on this range.
For each mid speed in our search:
- We calculate the total time required using this
midspeed. The calculation is the same as in the brute-force approach: sum the ceiling of travel times for the firstn-1trains and add the exact travel time for the last train. - If the calculated time is less than or equal to
hour, it means thismidspeed is a potential answer. Since we are looking for the minimum speed, we try to find an even smaller valid speed by narrowing our search to the lower half (high = mid - 1). We storemidas our current best answer. - If the calculated time is greater than
hour, themidspeed is too slow. We must increase the speed, so we narrow our search to the upper half (low = mid + 1).
The search continues until the low and high pointers cross. The last valid speed we recorded is the minimum integer speed required. If no speed within the search range is valid, we return -1.
An initial check can be performed as an optimization: the total time will always be greater than n-1 for any finite speed (since each of the first n-1 trips takes at least 1 hour after waiting). If the given hour is less than or equal to n-1, it's impossible to arrive on time, so we can immediately return -1.
class Solution { public int minSpeedOnTime(int[] dist, double hour) { int n = dist.length; // Optimization: If hour is too small, it's impossible. // Each of the first n-1 trips takes at least 1 hour. if (hour <= (double) n - 1 && n > 1) { return -1; } int low = 1; int high = 10000000; // Given constraint on the answer int minSpeed = -1; while (low <= high) { int mid = low + (high - low) / 2; // mid will not be 0 since low starts at 1. if (canArriveOnTime(dist, mid, hour)) { minSpeed = mid; high = mid - 1; // Try for a smaller speed } else { low = mid + 1; // Speed is too slow, need to increase } } return minSpeed; } private boolean canArriveOnTime(int[] dist, int speed, double hour) { double totalTime = 0.0; for (int i = 0; i < dist.length - 1; i++) { totalTime += Math.ceil((double) dist[i] / speed); } totalTime += (double) dist[dist.length - 1] / speed; return totalTime <= hour; }}Complexity
Time
O(N * log(K)), where `N` is the number of trains and `K` is the size of the speed search range (10^7). The `log(K)` factor comes from binary search, and for each step, we do an O(N) calculation. This is very efficient.
Space
O(1), as the binary search is performed in-place and the helper function uses constant extra space.
Trade-offs
Pros
Highly efficient, with a logarithmic time complexity with respect to the search range.
Guaranteed to find the optimal solution and pass within the time limits.
Cons
Slightly more complex to conceptualize than a linear search.
Relies on correctly identifying the monotonic property of the problem.
Solutions
Solution
boolean check ( int x ) { } int search ( int left , int right ) { while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if ( check ( mid )) { left = mid ; } else { right = mid - 1 ; } } return left ; }/** * @param {number[]} dist * @param {number} hour * @return {number} */ var minSpeedOnTime = function (dist, hour) { if (dist.length > Math.ceil(hour)) return -1; let left = 1, right = 10 ** 7; while (left < right) { let mid = (left + right) >> 1; if (arriveOnTime(dist, mid, hour)) { right = mid; } else { left = mid + 1; } } return left; };function arriveOnTime(dist, speed, hour) { let res = 0.0; let n = dist.length; for (let i = 0; i < n; i++) { let cost = parseFloat(dist[i]) / speed; if (i != n - 1) { cost = Math.ceil(cost); } res += cost; } return res <= hour;}class Solution {public: int minSpeedOnTime(vector<int> &dist, double hour) { int left = 1, right = 1e7; while (left < right) { int mid = (left + right) >> 1; if (check(dist, mid, hour)) { right = mid; } else { left = mid + 1; } } return check(dist, left, hour) ? left : -1; } bool check(vector<int> &dist, int speed, double hour) { double res = 0; for (int i = 0; i < dist.size(); ++i) { double cost = dist[i] * 1.0 / speed; res += (i == dist.size() - 1 ? cost : ceil(cost)); } return res <= hour; }};class Solution: def minSpeedOnTime(self, dist: List[int], hour: float) -> int: def check(speed): res = 0 for i, d in enumerate(dist): res += (d / speed) if i == len(dist) - 1 else math . ceil(d / speed) return res <= hour r = 10 ** 7 + 1 ans = bisect_left(range(1, r), True, key=check) + 1 return - 1 if ans == r else ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.