You are given n train rides with distances dist[i]. Each train departs at an integer hour, so you must wait until the next whole hour to board the next train (except for the last ride). Given a time limit hour, return the minimum positive integer speed such that you can arrive on time, or -1 if impossible.

Examples

Example 1:

Input: dist = [1,3,2], hour = 6
Output: 1
Explanation: At speed 1: ceil(1/1)=1 + ceil(3/1)=3 + 2/1=2 = 6 ≤ 6 ✓

Example 2:

Input: dist = [1,3,2], hour = 2.7
Output: 3
Explanation: At speed 3: ceil(1/3)=1 + ceil(3/3)=1 + 2/3≈0.67 = 2.67 ≤ 2.7 ✓

Example 3:

Input: dist = [1,3,2], hour = 1.9
Output: -1
Explanation: Need at least n-1 = 2 hours for waiting, but 1.9 < 2.

Constraints

  • 1 <= n <= 10^5
  • 1 <= dist[i] <= 10^5
  • 1 <= hour <= 10^9
  • hour has at most two decimal places

Thinking Process

Impossible Case

We must take n trains. Between each pair we wait until the next integer hour, so we need at least n - 1 hours just for the first n - 1 rides (minimum 1 hour each). If hour <= n - 1, it’s impossible.

Monotonic Property

As speed increases, total time decreases. This means:

  • If speed k is fast enough, any speed > k also works
  • If speed k is too slow, any speed < k also fails

This is a monotonic predicate – perfect for binary search on the answer.

Feasibility Check

At speed k, the total time is:

$t = sum_{i=0}^{n-2} leftlceil frac{text{dist}[i]}{k} rightrceil + frac{text{dist}[n-1]}{k}

  • First n - 1 rides: round up (must wait for next integer hour)
  • Last ride: exact time (no waiting after)

Integer ceiling trick: \lceil a/b \rceil = (a + b - 1) / b using integer division.

Walk-through

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

Binary search: left=1, right=10^7

mid=5000000: t = 1 + 1 + 0.0000004 = 2.0 ≤ 2.7 → right=5000000
...converges...
mid=3: t = ceil(1/3) + ceil(3/3) + 2/3 = 1 + 1 + 0.67 = 2.67 ≤ 2.7 → right=3
mid=2: t = ceil(1/2) + ceil(3/2) + 2/2 = 1 + 2 + 1.0 = 4.0 > 2.7  → left=3

Answer: left = 3 ✓
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(\log n) O(1) Sorted array, left <= right
Lower / upper bound O(\log n) O(1) First/last position, insert index
Binary search on rotated array O(\log n) O(1) Identify sorted half, discard other
Binary search on answer O(n \log M) O(1) Monotonic predicate over search space

Solution

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

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: ### Impossible Case

How the code works:

  • If speed k is fast enough, any speed > k also works
  • If speed k is too slow, any speed < k also fails
  • First n - 1 rides: round up (must wait for next integer hour)
  • Last ride: exact time (no waiting after)

Walkthrough — input dist = [1,3,2], hour = 6, expected output 1:

At speed 1: ceil(1/1)=1 + ceil(3/1)=3 + 2/1=2 = 6 ≤ 6 ✓

Why M = 10^7?

Maximum distance is 10^5 and hour can have two decimal places, so the last ride could need a speed up to 10^5 / 0.01 = 10^7$ in the worst case.

Common Mistakes

  • Not handling the impossible case (hour <= n - 1) – leads to infinite binary search
  • Using floating-point ceiling (ceil(dist[i] / (double)k)) instead of integer ceiling – precision issues
  • Applying ceiling to the last ride (the last ride doesn’t need to round up)
  • Wrong search range: upper bound too small misses edge cases with tight time limits

Key Takeaways

  • “Find minimum X such that predicate holds” with monotonic feasibility = binary search on the answer
  • The integer ceiling trick (a + b - 1) / b avoids floating-point precision issues
  • Treating the last element differently (no rounding) is a common pattern in scheduling/train problems

References

Template Reference