Minimum Speed to Arrive on Time solution and explanation
Google
9 more videos on this problem
Minimum Speed to Arrive on Time | Binary Search | INTUITION | Online Assessment | Leetcode-1870codestorywithMIK · 30:40 · 8K views
1870. Minimum Speed to Arrive on Time | LEETCODE WEEKLY CONTEST 242 | LEETCODEcode Explainer · 12:24 · 6K views
Minimum Speed to Arrive on Time | LeetCode 1870 | Coders CampCoders Camp · 8:42 · 2K views
LeetCode 1870 Minimum Speed to Arrive on TimeJeevan Kumar - Cracckify · 10:55 · 2K views
Minimum Speed to Arrive on Time | Binary Search on Answer | Python, C++, JavaRisingBrain · 16:17 · 1K views
1870. Minimum Speed to Arrive on Time (Leetcode Medium)Programming Live with Larry · 26:31 · 732 views
Minimum Speed to Arrive on Time - Leetcode 1870Algorithms Casts · 15:33 · 504 views
Daily Leetcode #1212: Jul 26, 2023 - 1870. Minimum Speed to Arrive on TimeProgramming Live with Larry · 24:08 · 428 views
Minimum Speed to Arrive on Time || Leetcode 1870 || JAVAPersistent Coder · 14:08 · 407 views
LEETCODE POD - 1870. Minimum Speed to Arrive on TimeShubhi agarwal · 10:19 · 249 views
The problem
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.
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.
import math
def minSpeedOnTime(dist, hour):
left, right = 1, 10000000
while left < right:
mid = (left + right) // 2
time = 0.0
for i in range(len(dist)):
if i < len(dist) - 1:
time += math.ceil(dist[i] / mid)
else:
time += dist[i] / mid
if time <= hour:
right = mid
else:
left = mid + 1
return -1 if left == 10000000 else left
# Example usage:
dist = [1, 3, 2]
hour = 6
print(minSpeedOnTime(dist, hour))public class MinSpeed {
public static int minSpeedOnTime(int[] dist, double hour) {
int left = 1, right = 10000000;
while (left < right) {
int mid = (left + right) / 2;
double time = 0;
for (int i = 0; i < dist.length; i++) {
if (i < dist.length - 1) {
time += Math.ceil((double) dist[i] / mid);
} else {
time += (double) dist[i] / mid;
}
}
if (time <= hour) {
right = mid;
} else {
left = mid + 1;
}
}
return left == 10000000 ? -1 : left;
}
public static void main(String[] args) {
int[] dist = {1, 3, 2};
double hour = 6;
System.out.println(minSpeedOnTime(dist, hour));
}
}#include <iostream>
#include <vector>
#include <cmath>
int minSpeedOnTime(std::vector<int>& dist, double hour) {
int left = 1, right = 1e7;
while (left < right) {
int mid = (left + right) / 2;
double time = 0.0;
for (int i = 0; i < dist.size(); ++i) {
if (i < dist.size() - 1) {
time += std::ceil((double)dist[i] / mid);
} else {
time += (double)dist[i] / mid;
}
}
if (time <= hour) {
right = mid;
} else {
left = mid + 1;
}
}
return left == 1e7 ? -1 : left;
}
int main() {
std::vector<int> dist = {1, 3, 2};
double hour = 6;
std::cout << minSpeedOnTime(dist, hour) << std::endl;
return 0;
}function minSpeedOnTime(dist, hour) {
let left = 1, right = 10000000;
while (left < right) {
let mid = Math.floor((left + right) / 2);
let time = 0;
for (let i = 0; i < dist.length; ++i) {
if (i < dist.length - 1) {
time += Math.ceil(dist[i] / mid);
} else {
time += dist[i] / mid;
}
}
if (time <= hour) {
right = mid;
} else {
left = mid + 1;
}
}
return left === 10000000 ? -1 : left;
}
// Example usage:
let dist = [1, 3, 2];
let hour = 6;
console.log(minSpeedOnTime(dist, hour));#include <stdio.h>
#include <math.h>
int minSpeedOnTime(int* dist, int distSize, double hour) {
int left = 1, right = 10000000;
while (left < right) {
int mid = (left + right) / 2;
double time = 0.0;
for (int i = 0; i < distSize; ++i) {
if (i < distSize - 1) {
time += ceil((double)dist[i] / mid);
} else {
time += (double)dist[i] / mid;
}
}
if (time <= hour) {
right = mid;
} else {
left = mid + 1;
}
}
return left == 10000000 ? -1 : left;
}
int main() {
int dist[] = {1, 3, 2};
double hour = 6;
int result = minSpeedOnTime(dist, 3, hour);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int MinSpeedOnTime(int[] dist, double hour) {
int left = 1, right = 10000000;
while (left < right) {
int mid = (left + right) / 2;
double time = 0.0;
for (int i = 0; i < dist.Length; ++i) {
if (i < dist.Length - 1) {
time += Math.Ceiling((double)dist[i] / mid);
} else {
time += (double)dist[i] / mid;
}
}
if (time <= hour) {
right = mid;
} else {
left = mid + 1;
}
}
return left == 10000000 ? -1 : left;
}
public static void Main() {
int[] dist = {1, 3, 2};
double hour = 6;
Console.WriteLine(new Solution().MinSpeedOnTime(dist, hour));
}
}The solution utilizes binary search to efficiently determine the minimum speed necessary to reach the destination within the hour limit. Python's float arithmetic and math.ceil function ascertain the feasibility of each candidate speed until convergence.
Time Complexity: O(n log k).
Space Complexity: O(1).
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).
function minSpeedOnTime(dist: number[], hour: number): number {
if (dist.length > Math.ceil(hour)) {
return -1;
}
const n = dist.length;
const m = 10 ** 7;
const check = (v: number): boolean => {
let s = 0;
for (let i = 0; i < n; ++i) {
const t = dist[i] / v;
s += i === n - 1 ? t : Math.ceil(t);
}
return s <= hour;
};
let [l, r] = [1, m + 1];
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}func minSpeedOnTime(dist []int, hour float64) int {
if float64(len(dist)) > math.Ceil(hour) {
return -1
}
const m int = 1e7
n := len(dist)
ans := sort.Search(m+1, func(v int) bool {
v++
s := 0.0
for i, d := range dist {
t := float64(d) / float64(v)
if i == n-1 {
s += t
} else {
s += math.Ceil(t)
}
}
return s <= hour
}) + 1
if ans > m {
return -1
}
return ans
}class Solution {
fun minSpeedOnTime(dist: IntArray, hour: Double): Int {
val n = dist.size
if (n > Math.ceil(hour)) {
return -1
}
val m = 1e7.toInt()
var left = 1
var right = m + 1
while (left < right) {
val middle = (left + right) / 2
var time = 0.0
dist.forEachIndexed { i, item ->
val t = item.toDouble() / middle
time += if (i == n - 1) t else Math.ceil(t)
}
if (time > hour) {
left = middle + 1
} else {
right = middle
}
}
return if (left > m) -1 else left
}
}impl Solution {
pub fn min_speed_on_time(dist: Vec<i32>, hour: f64) -> i32 {
if dist.len() as f64 > hour.ceil() {
return -1;
}
const M: i32 = 10_000_000;
let (mut l, mut r) = (1, M + 1);
let n = dist.len();
let check = |v: i32| -> bool {
let mut s = 0.0;
for i in 0..n {
let t = dist[i] as f64 / v as f64;
s += if i == n - 1 { t } else { t.ceil() };
}
s <= hour
};
while l < r {
let mid = (l + r) / 2;
if check(mid) {
r = mid;
} else {
l = mid + 1;
}
}
if l > M {
-1
} else {
l
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(n log k). |
| Binary Search | – |
Complexity analysis
| 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 |
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.