Minimum Speed to Arrive on Time — Binary Search on Speed [LC 1870, Google]

Problem Statement#

You are given n train rides with distances dist[i]. Each ride except the last departs only on the hour (ceiling division for wait time). Find the minimum positive integer speed v to complete all rides within hour hours, or return -1 if impossible.

Constraints:

• n == dist.length
• 1 <= n <= 10^5
• 1 <= dist[i] <= 10^5
• 1 <= hour <= 10^9
• hour is a floating-point number with at most two decimal places

Input:  dist = [1,3,2], hour = 6
Output: 1

Input:  dist = [1,3,2], hour = 2.7
Output: 3

Input:  dist = [1,3,2], hour = 1.9
Output: -1

Why This Problem Matters#

LC 1870 is a clean binary-search-on-answer problem that adds a subtle twist: the time formula is not uniform across all rides. All rides except the last use ceiling division (you must wait for the next train hour after each intermediate ride). Only the last ride uses exact division (no waiting after arrival). Missing this distinction is the most common error.

Google and Amazon ask this problem because it combines the binary-search-on-answer template with careful mathematical reasoning about integer vs floating-point division.

The Core Insight#

Binary search on speed v in [1, 10^7] (problem constraints cap speed at 10^7). For a given speed v:

• Time for intermediate rides: sum(ceil(dist[i] / v) for i in range(n-1)) — ceiling because you wait for the next hour
• Time for the last ride: dist[-1] / v — exact division, no waiting
• Feasible if total time <= hour

Impossibility check: If there are n rides, you need at least n - 1 full hours for the intermediate rides (at minimum speed, each intermediate ride takes at least 1 hour). So if n - 1 >= hour, it is impossible unless n == 1.

More precisely: the minimum possible time with infinite speed is n - 1 + epsilon (n-1 full hours of waiting plus near-zero ride time). So if hour <= n - 1, return -1 (when n > 1).

Visual Dry Run#

dist = [1, 3, 2], hour = 2.7

Binary search: lo=1, hi=10^7. Converges to 3.

Solution (Optimal)#

import math
 
class Solution:
    def minSpeedOnTime(self, dist: list[int], hour: float) -> int:
        n = len(dist)
 
        # Need at least n-1 full hours for intermediate rides
        # If hour <= n-1, impossible (need strictly more than n-1 hours)
        if hour <= n - 1:
            return -1
 
        def feasible(speed: int) -> bool:
            total = 0.0
            for i in range(n - 1):
                total += math.ceil(dist[i] / speed)  # wait for next hour
            total += dist[-1] / speed                  # last ride: exact time
            return total <= hour
 
        lo, hi = 1, 10**7
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if feasible(mid):
                hi = mid
            else:
                lo = mid + 1
 
        return lo

var minSpeedOnTime = function(dist, hour) {
    const n = dist.length;
 
    // Impossible if not enough time for n-1 full intermediate waits
    if (hour <= n - 1) return -1;
 
    function feasible(speed) {
        let total = 0;
        for (let i = 0; i < n - 1; i++) {
            total += Math.ceil(dist[i] / speed);  // ceiling for intermediate rides
        }
        total += dist[n - 1] / speed;              // exact time for last ride
        return total <= hour;
    }
 
    let lo = 1, hi = 1e7;
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
 
    return lo;
};

Time: O(n log(max_speed)) — O(log 10^7) ≈ 23 iterations, each O(n) feasibility scan Space: O(1) — only loop variables

Common Mistakes#

• Using exact division for ALL rides (forgetting the ceiling for intermediate rides) — gives time values that are too small.
• Using ceiling division for the LAST ride — the last ride does not need to wait, so exact division is correct.
• Wrong impossibility check: checking n > ceil(hour) — the correct check is hour <= n - 1 (you need MORE than n-1 hours strictly).
• Setting hi = max(dist) — too small; speed can be up to 10^7 per the problem constraints.
• Using integer division in Python for the last ride — use dist[-1] / speed (float division), not dist[-1] // speed.

Interview Tips#

• State the time formula first: "intermediate rides use ceil(d/v), last ride uses d/v."
• Explain the impossibility condition: "with n rides, you need at least n-1 wait hours, so if hour <= n-1, it is impossible."
• Use integer ceiling division (d + v - 1) // v instead of math.ceil(d/v) to avoid floating-point issues in intermediate calculations.
• Mention the search bound: "the constraint says speed <= 10^7, so hi = 10^7 is the correct upper bound."

Follow-up Questions#

• What if the last ride also has a wait time? Replace the last ride calculation with ceil(dist[-1] / speed) too. The impossibility condition stays the same.
• LC 875 (Koko Eating Bananas): Same template, simpler feasibility (no ceiling/exact distinction).
• What if hour has more decimal precision? Multiply hour by 100 to convert to integer centihours, adjust all time calculations accordingly.
• Why is max speed 10^7? The maximum distance is 10^5 and minimum hour is 0.01 (two decimal places), so minimum needed speed is 10^5 / 0.01 = 10^7.

Key Takeaways#

• LC 1870 is binary search on speed in [1, 10^7]: the feasibility check computes total travel time and compares to hour.
• Critical asymmetry: intermediate rides use ceiling division (must wait for next train hour); only the last ride uses exact division.
• Impossibility condition: hour <= n - 1 (need strictly more than n-1 hours even at infinite speed due to n-1 intermediate waits).
• Use while lo < hi with hi = mid on success and lo = mid + 1 on failure — converges to the minimum feasible speed.
• Set hi = 10^7 (not max(dist)) — the problem constraints cap speed at 10^7 and this is the correct bound.
• Integer ceiling formula (d + v - 1) // v avoids floating-point ceiling errors for large distances.
• This template is structurally identical to LC 875, LC 1011, and LC 1482 — the only novelty is the mixed ceiling/exact time formula.