Coding Interview PatternsMinimum Speed to Arrive on Time
MediumModified Binary Search
Minimum Speed to Arrive on Time
Explanation & Solution
Description
You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute, you must take n trains in sequential order. You are also given an integer array dist, where dist[i] describes the distance of the i-th train ride.
Each train can only depart at an integer hour, so you may need to wait between trains. The last train has no such restriction.
Return the minimum positive integer speed (in km/hr) that all trains must travel at for you to reach the office on time, or -1 if it is impossible.
Input:dist = [1, 3, 2], hour = 6
0
1
1
3
2
2
Output: 1
Explanation: At speed 1: train 1 takes 1 hr, train 2 takes 3 hrs, train 3 takes 2 hrs = 6 total.
Constraints
1 <= dist.length <= 10^51 <= dist[i] <= 10^51 <= hour <= 10^9- There will be at most two digits after the decimal point in
hour
Approach
Modified Binary Search pattern
1. Check Impossibility
- With
ntrains, you need at leastn - 1integer hours for the firstn - 1trains (each takes at least 1 hour and departs at integer times). Ifhour <= n - 1, return-1.
2. Binary Search on Speed
- Search over speeds
[1, 10^7]. - For candidate speed
mid, compute total travel time: - For each train except the last:
ceil(dist[i] / mid)(must depart at integer hours). - For the last train:
dist[n-1] / mid(no rounding needed).
3. Feasibility Check
- If total time
<= hour, speed works → try slower:hi = mid. - Otherwise, need faster:
lo = mid + 1.
4. Return the Minimum Speed
🧠 Key Insight
- The last train is special: it doesn't need to arrive at an integer hour, so we use exact division for it.
Time
O(n · log(10^7)) ≈ O(n · 23).Space
O(1).Visualization
Input:
[1, 3, 2], hour = 6
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
99 steps