Minimum Speed to Arrive on Time: Binary Search on the Answer

Minimum Speed to Arrive on Time is LeetCode 1870, and it is another great example of binary search on the answer space. You are not searching through an array for a target. You are searching through all possible train speeds to find the smallest one that gets you to the office on time. If you have seen Koko Eating Bananas, the structure will feel familiar. The feasibility check is different, but the binary search skeleton is identical.

If you have worked through the binary search pattern, you already know the template. This problem is a direct application of the "search on the answer" variant described there.

The problem

You are given a floating-point number hour representing the maximum time you have to reach the office. You are also given an integer array dist where dist[i] is the distance of the ith train ride. You must take the trains in order.

Here is the catch: each train only departs at integer hours. So if you finish a ride partway through an hour, you wait until the next whole hour to board the next train. The only exception is the last train, where you arrive as soon as you finish the ride.

Return the minimum positive integer speed such that you can reach the office within hour hours, or -1 if it is impossible.

Example: dist = [1, 3, 2], hour = 6.

At speed 1, the total time is ceil(1/1) + ceil(3/1) + 2/1 = 1 + 3 + 2 = 6.0 hours. That is exactly 6, so it works. Since 1 is the smallest possible speed, the answer is 1.

The brute force approach

You could try every possible speed starting from 1 and going up. For each speed, compute the total travel time. Return the first speed where the time fits within hour.

def min_speed_brute(dist, hour):
    import math
    for speed in range(1, 10**7 + 1):
        total = 0.0
        for i in range(len(dist) - 1):
            total += math.ceil(dist[i] / speed)
        total += dist[-1] / speed
        if total <= hour:
            return speed
    return -1

This works, but it checks up to 10^7 speeds in the worst case, and for each speed it loops through all n distances. That is O(10^7 * n), which is too slow.

The key insight: monotonic feasibility

Here is the observation that makes binary search work. If you can arrive on time at speed s, you can definitely arrive at speed s + 1, and s + 2, and any faster speed. If you cannot arrive at speed s, you also cannot arrive at s - 1 or anything slower.

That is a monotonic condition. The answer space [1, 10^7] splits neatly into two regions:

• Infeasible: speeds 1 through answer - 1 (too slow, total time exceeds hour)
• Feasible: speeds answer through 10^7 (fast enough, total time is at most hour)

When you have a monotonic condition over a range, binary search finds the boundary in O(log n) time.

The feasibility check

Before writing the binary search, you need a function that answers: "Can you arrive on time at speed s within hour hours?"

def can_arrive(dist, speed, hour):
    import math
    total = 0.0
    for i in range(len(dist) - 1):
        total += math.ceil(dist[i] / speed)
    total += dist[-1] / speed
    return total <= hour

For each ride except the last, ceil(dist[i] / speed) gives the hours spent (including waiting for the next departure). For the last ride, you use the exact value dist[-1] / speed since there is no next train to wait for. If the total is at most hour, the speed is feasible. This runs in O(n) time.

Visual walkthrough

Let's binary search for the minimum valid speed with dist = [1, 3, 2] and hour = 2.7. The search range is [1, 10] (using a small range for clarity).

Four steps. Instead of checking all 10 possible speeds, we checked 3 and found the answer. With the full range of [1, 10^7], binary search still takes at most about 23 steps. That is the power of O(log n).

The code

Here is the complete Python solution for LeetCode 1870, minimum speed to arrive on time:

def min_speed_on_time(dist, hour):
    import math
    n = len(dist)
    if hour <= n - 1:
        return -1

    lo, hi = 1, 10**7

    while lo < hi:
        mid = lo + (hi - lo) // 2
        total = 0.0
        for i in range(n - 1):
            total += math.ceil(dist[i] / mid)
        total += dist[-1] / mid

        if total <= hour:
            hi = mid
        else:
            lo = mid + 1

    return lo

Let's walk through the important decisions.

Early return when hour is at most n - 1. If you have n trains, you need at least n - 1 whole hours just for the waiting between rides (each of the first n - 1 rides takes at least 1 hour due to ceiling). Plus you need some time for the last ride. So if hour is not greater than n - 1, it is impossible regardless of speed.

lo = 1, hi = 10^7. The minimum possible speed is 1. The problem guarantees the answer, if it exists, is at most 10^7. This is given in the constraints.

while lo < hi, not while lo <= hi. We are narrowing down to a single answer. When lo == hi, that is our answer.

if total <= hour: hi = mid. If the current speed works, it might be the answer, or a slower speed might also work. So we keep mid in the range and search left.

else: lo = mid + 1. If the current speed does not work, we need something strictly faster. So we move lo past mid.

Return lo. When the loop ends, lo == hi and that is the minimum feasible speed.

Complexity analysis

Time: O(n * log(10^7)). The binary search runs O(log(10^7)) iterations, which is about 23 iterations. Each iteration computes the feasibility check in O(n) time by looping through all distances.

Space: O(1). Just a few variables. No extra data structures.

For the constraints in LeetCode 1870 (n up to 10^5, dist[i] up to 10^5), this is about 23 * 100,000 = 2,300,000 operations. Very fast.

Edge cases to watch for

• Impossible case: If hour is at most n - 1, return -1. You cannot take n train rides in that time regardless of speed since you need at least one hour per non-last ride.
• Single train ride: dist = [5], hour = 2.5. There is only one ride and no rounding, so the answer is ceil(5 / 2.5) = 2.
• hour is barely enough: dist = [1, 1, 100000], hour = 2.01. The first two rides each take 1 hour at any speed. That leaves 0.01 hours for the last 100,000 km. You need speed 100000 / 0.01 = 10,000,000.
• All distances equal: dist = [3, 3, 3], hour = 4. At speed 3, time = 1 + 1 + 1 = 3. At speed 2, time = 2 + 2 + 1.5 = 5.5. At speed 3, it works. Binary search finds this efficiently.

The building blocks

This problem is built on one core building block: binary-search-on-answer.

The skeleton is the standard binary search template, but instead of searching a sorted array for a target, you are searching a range of candidate answers for the smallest one that satisfies a condition.

while lo < hi:
    mid = lo + (hi - lo) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

The only thing that changes from problem to problem is the feasibility function. For Koko Eating Bananas, it checks whether Koko can eat all the piles. For this problem, it checks whether you can arrive on time. The binary search structure is identical.

This same binary-search-on-answer pattern shows up in several related problems:

• Koko Eating Bananas (LeetCode 875): binary search on eating speed
• Capacity to Ship Packages Within D Days (LeetCode 1011): binary search on ship capacity
• Split Array Largest Sum (LeetCode 410): binary search on the maximum subarray sum

In every case, the structure is the same: define the range, write the feasibility check, binary search.

From understanding to recall

The logic is clean. Binary search the speed range, check feasibility at each midpoint, narrow down to the smallest valid speed. You probably get it right now.

But try writing it cold in an interview three weeks from now. Was it lo < hi or lo <= hi? Do you round up the last ride or not? What is the early return condition? These small details are exactly the kind of thing that slips under pressure.

Spaced repetition is designed for this. You type the solution from scratch today, then again tomorrow, then in three days. After a few rounds, the while lo < hi and hi = mid pattern is muscle memory. The special handling of the last train ride becomes automatic. You do not have to rederive it. You just write it.

LeetCode 1870 is a perfect SRS candidate because the code is short (about 12 lines), the pattern is reusable across many problems, and the feasibility check has a subtle twist (the last ride) that is easy to forget if you have not drilled it.

Related posts

• Binary Search: More Than Finding a Number - The full binary search pattern guide, including the search-on-answer variant this problem is built on
• Koko Eating Bananas - The classic binary-search-on-answer problem with the same template
• Find First and Last Position - Another binary search variant that exercises left-bound and right-bound searches