DSA sheet · Binary Search · Binary search on answer

Minimum Speed to Arrive on Time

The third problem of the binary search on answer pattern. It looks a lot like Koko Eating Bananas (find the slowest speed that's still fast enough), but with three twists the teacher focuses on: the time limit is a decimal number, the last train is not rounded up, and the upper limit of the search does not come from the array (it's 10⁷, straight from the problem statement). It can also be impossible, so we may have to return −1.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every speed from 1 to 10⁷
• Part B · Optimal: binary search on the speed
• Part C · Revision page

Part 0 · Before starting

Why binary search works at all

Binary search works whenever we have a yes/no question that is monotonic: as we move along the values, the answer is "no, no, no…" and then switches to "yes, yes, yes…" exactly once (or the reverse). Testing the middle value tells us which side of the middle the switch lies on, so we throw the other side away. A sorted array is one such case, but a range of numbers that we choose works just as well.

low, high, mid

• low, high: the ends of the part still being searched.
• mid: the middle value we test.
• while low <= high: the teacher explains why <= and not <: when low and high point at the same single speed, that speed still has to be tested. With < it would be skipped.

Why mid = low + (high - low) // 2?

In Java/C++, (low + high) / 2 can overflow if low + high goes past the int limit (about 2.1 × 10⁹). low + (high - low) / 2 never does. Here high is 10⁷ so it wouldn't overflow anyway, but the safe form is a good habit. Python ints never overflow; both forms give the same result.

The pattern: binary search on answer

1. Answer range: pick the smallest possible answer (low) and the largest we'd ever need (high).
2. Check function: check(speed) = "at this speed, do I reach the office in time?"
3. Monotonic: time = distance ÷ speed. Faster trains never take more time. So once a speed works, every faster speed works: no no no yes yes yes.
4. Which side to keep: we want the minimum speed. Yes at mid → save it, go left. No → go right.

speeds:     1 ........................................ 10^7
on time?:   no   no   no   no  YES  YES  YES  YES  YES
                               ^
                     the first YES = minimum speed
(if even 10^7 says "no", there is no YES at all → return -1)

Floor and ceiling

Ceiling = round up to the next whole number (ceil(1.5) = 2, ceil(2.0) = 2). Floor = round down. In Python, math.ceil(x) gives the ceiling, and for whole numbers (a + b - 1) // b gives ceil(a / b) without any decimals.

Part A · Brute force: try every speed from 1 to 10⁷

LeetCode 1870

1The question in simple words

You must reach the office within hour hours. hour is a decimal number (for example 2.7). To get there you take n trains one after another, in the given order. Train i travels dist[i] km. All trains run at the same speed, which you choose (a positive whole number, km per hour).

The catch: a train can only leave at a whole hour (1:00, 2:00, …). If a ride takes 1.5 hours, you wait 0.5 hours for the next train, which leaves at hour 2. So every ride except the last one effectively costs a whole number of hours (rounded up). After the last ride there is no next train to wait for, so its time counts exactly.

Return the minimum speed that gets you there on time, or −1 if no speed can.

2What the constraints tell us

• 1 <= n <= 10⁵, 1 <= dist[i] <= 10⁵.
• 1 <= hour <= 10⁹, with at most two digits after the decimal point (like 2.70 or 1.09).
• The answer will not exceed 10⁷. The teacher underlines this last line: it means 10⁷ itself can be the answer, and nothing above it ever is. This is where our high comes from.

3Intuition

Same as Koko: if you didn't know binary search, you'd try speed 1, then 2, then 3… and for each speed add up the travel time of all the trains. The first speed whose total time is within hour is the minimum, because we go upward. If none of them works, return −1.

4Building the logic from examples

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

At speed 1: 1 h + 3 h + 2 h = 6 h, and no waiting is needed (each ride ends on a whole hour). 6 ≤ 6 → speed 1 works. Nothing is slower than 1, so 1 is the answer.

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

At speed 3:

• Train 1: 1/3 = 0.33 h, but the next train leaves only at hour 1 → counts as 1 h.
• Train 2: 3/3 = 1 h → 1 h. Now we're at hour 2.
• Train 3 (last): 2/3 = 0.67 h → counted exactly, no waiting after it.

Total 2.67 h ≤ 2.7 → on time. (Speed 2 gives 1 + 2 + 1.0 = 4 h, too slow.) Answer 3.

Choosing low and high

• low = 1. Speed must be a positive integer; 0 or negative makes no sense.
• high = 10⁷. Not max(dist), not sum(dist) as in earlier problems. The statement itself promises the answer is at most 10⁷, so that's the upper limit.

Example 3: dist = [1, 3, 2], hour = 1.9 → −1 (the base case)

Try the fastest possible speed, 10⁷. Train 1: 0.0000001 h, but we wait → 1 h. Train 2: again → 1 h. Train 3: 2/10⁷ ≈ 0.0000002 h. Total ≈ 2.0000002 h. Even at top speed it's more than 1.9 → impossible → −1.

The teacher generalises: the first n − 1 trains each cost at least 1 whole hour, and the last one costs a bit more than 0. So the total is always more than n − 1 hours. With n = 3 the total is at least "2.something"; since hour has two decimals, the smallest hour that can work is 2.01. With n = 4, it's 3.01.

5Approach steps

1. (Optional) if hour <= n - 1 → return −1.
2. For each speed from 1 to 10⁷:
3. time = 0.0. For each train j: t = dist[j] / speed. If j is not the last index, add ceil(t); else add t.
4. If time ≤ hour → return this speed (first one = minimum).
5. After the loop → return −1.

6Code (Python)

import math

class Solution:
    def minSpeedOnTime(self, dist, hour):
        n = len(dist)
        if hour <= n - 1:                  # optional base case
            return -1
        for speed in range(1, 10**7 + 1):
            time = 0.0
            for j in range(n):
                t = dist[j] / speed           # ride time as a decimal
                if j != n - 1:
                    time += math.ceil(t)      # wait for the whole hour
                else:
                    time += t                 # last ride: exact
            if time <= hour:
                return speed                  # first that works = minimum
        return -1

7Code line by line

8Dry run

dist = [1, 3, 2], hour = 2.7. Base case: 2.7 > 2, so continue.

speed   :   1     2     3     4     5   ...   10^7
time    :  6.0   4.0   2.67  2.5   2.4  ...   2.0000002
<= 2.7? :  no    no    YES   YES   YES  ...   YES
                       ^ first YES = 3

9Complexity & remember

• Outer loop: up to 10⁷ speeds (from the statement). Inner loop: n ≤ 10⁵ trains. Multiplied: 10¹² → TLE.
• The inner loop cannot be reduced: to know the total time we must look at every train. The outer loop is the one to fix.
• Space O(1).

Part B · Optimal: binary search on the speed

1The question

Same as Part A. The time calculation moves into a function, canReach(dist, hour, speed), and the outer loop becomes a binary search.

2Constraints

The range 1 … 10⁷ is sorted (it's a number line), and halving it takes only log₂(10⁷) ≈ 24 steps.

3Intuition

Why test speeds one after another when they're sorted and the yes/no answer flips only once? Test the middle speed and drop half. That's the whole change. This is also why the teacher asked us to put the time calculation in its own function: so we can call it with any mid.

4Building the decisions

• canReach(mid) is True: mid is on time, so it may be the answer. Save it in ans. We want the minimum, so look left: high = mid - 1.
• canReach(mid) is False: say we had 6 hours and mid took 8. To cut the time we can't change the distance (time = distance ÷ speed), so we must raise the speed: low = mid + 1.
• ans starts at −1. If no speed ever works, it's never overwritten, and −1 is exactly what the question wants for "impossible".

5Approach steps

1. (Optional) if hour <= n - 1 → −1.
2. low = 1, high = 10**7, ans = -1.
3. While low <= high: mid = low + (high − low) // 2.
4. If canReach(mid): ans = mid, high = mid − 1. Else: low = mid + 1.
5. Return ans.

6Code (Python)

import math

class Solution:
    def minSpeedOnTime(self, dist, hour):
        if hour <= len(dist) - 1:          # optional base case
            return -1
        low, high = 1, 10**7
        ans = -1                           # stays -1 if nothing works
        while low <= high:
            mid = low + (high - low) // 2  # mid = speed to test
            if self.canReach(dist, hour, mid):
                ans = mid                  # on time: remember it
                high = mid - 1             # try slower
            else:
                low = mid + 1              # late: go faster
        return ans

    def canReach(self, dist, hour, speed):
        n = len(dist)
        time = 0.0
        for j in range(n):
            t = dist[j] / speed
            if j != n - 1:
                time += math.ceil(t)       # wait for the next whole hour
            else:
                time += t                  # last ride: exact
        return time <= hour

class Solution:
    def minSpeedOnTime(self, dist, hour):
        H = round(hour * 100)              # hour in hundredths, e.g. 2.7 -> 270
        n = len(dist)
        if H <= 100 * (n - 1):             # base case: hour <= n - 1
            return -1
        low, high = 1, 10**7
        ans = -1
        while low <= high:
            mid = low + (high - low) // 2
            if self.canReach(dist, H, mid):
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        return ans

    def canReach(self, dist, H, speed):
        full = 0
        for j in range(len(dist) - 1):     # every ride except the last
            full += (dist[j] + speed - 1) // speed     # ceil, in whole hours
        # full + dist[-1] / speed <= H / 100, multiplied by 100 * speed:
        return 100 * (full * speed + dist[-1]) <= H * speed

7Code line by line

8Dry run (hand table)

dist = [1, 3, 2], hour = 2.7. low = 1, high = 10⁷, ans = −1.

The last few steps on the speeds 1 … 8 (yellow = mid, grey = thrown away):

With hour = 6, the same walk continues one step further: speed 2 also works (4.0 ≤ 6), and then speed 1 (6.0 ≤ 6), so the answer is 1. With hour = 1.9, the base case returns −1 at once (and without it, every check says "no", so ans stays −1).

9Complexity & remember

• Time O(n × log(10⁷)) ≈ 24 × 10⁵ = 2.4 × 10⁶ → passes.
• Space O(1).

Part C · Revision page

s = Solution()
print(s.minSpeedOnTime([1, 3, 2], 6))          # 1
print(s.minSpeedOnTime([1, 3, 2], 2.7))        # 3
print(s.minSpeedOnTime([1, 3, 2], 1.9))        # -1
print(s.minSpeedOnTime([1, 1, 100000], 2.01))  # 10000000
print(s.minSpeedOnTime([50, 7], 1.14))         # 50 (float version says 51)

Based on this video: Minimum Speed to Arrive on Time | Binary Search on Answer