Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search
[1,3,2] 6
[1,3,2] 2.7
[1,3,2] 1.9
maximum-candies-allocated-to-k-children)minimum-skips-to-arrive-at-meeting-on-time)minimum-time-to-complete-trips)the-latest-time-to-catch-a-bus)minimize-maximum-of-array)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1870: Minimum Speed to Arrive on Time
class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
if (dist.length > Math.ceil(hour)) {
return -1;
}
final int m = (int) 1e7;
int l = 1, r = m + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(dist, mid, hour)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}
private boolean check(int[] dist, int v, double hour) {
double s = 0;
int n = dist.length;
for (int i = 0; i < n; ++i) {
double t = dist[i] * 1.0 / v;
s += i == n - 1 ? t : Math.ceil(t);
}
return s <= hour;
}
}
// Accepted solution for LeetCode #1870: Minimum Speed to Arrive on Time
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
}
# Accepted solution for LeetCode #1870: Minimum Speed to Arrive on Time
class Solution:
def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
def check(v: int) -> bool:
s = 0
for i, d in enumerate(dist):
t = d / v
s += t if i == len(dist) - 1 else ceil(t)
return s <= hour
if len(dist) > ceil(hour):
return -1
r = 10**7 + 1
ans = bisect_left(range(1, r), True, key=check) + 1
return -1 if ans == r else ans
// Accepted solution for LeetCode #1870: Minimum Speed to Arrive on Time
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
}
}
}
// Accepted solution for LeetCode #1870: Minimum Speed to Arrive on Time
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;
}
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.