LeetCode 1870 - Minimum Speed to Arrive on Time

The problem asks us to find the minimum constant speed (in kilometers per hour) required to travel a sequence of train rides and reach the destination within a given floating-point hour.

leetcodemediumarraybinary-search

LeetCode Problem 1870

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to find the minimum constant speed (in kilometers per hour) required to travel a sequence of train rides and reach the destination within a given floating-point hour. Each train has a fixed distance, and each subsequent train can only depart at the next integer hour. This waiting period after each ride creates a non-linear dependency on the travel time for each segment.

The input consists of an integer array dist where dist[i] is the distance of the i-th train ride, and a float hour representing the total allowed time. The output is the minimum integer speed that allows arriving on time, or -1 if it is impossible. Constraints guarantee that distances and the number of trains can be large (up to 10^5), and hour has at most two decimal places, which hints at potential precision issues if we use floating-point arithmetic carelessly.

Key edge cases include scenarios where hour is smaller than the number of trains, which would make it impossible to arrive on time due to mandatory rounding up to the next integer for all but the last train.

Approaches

A brute-force approach would try every speed starting from 1 upwards, computing the total travel time for each speed and returning the first speed that allows arrival within hour. This approach works but is too slow given the constraints (speed can go up to 10^7 and distances can be large).

The optimal approach uses binary search on speed. The key insight is that travel time is monotonically decreasing as speed increases. This allows us to efficiently search for the minimum speed that satisfies the time constraint. At each candidate speed, we calculate the total travel time, taking the ceiling of the time for each train except the last one.

Approach Time Complexity Space Complexity Notes
Brute Force O(MaxSpeed * n) O(1) Iterate over all possible speeds until a feasible one is found
Optimal O(n * log(MaxSpeed)) O(1) Use binary search on speed range to find minimum feasible speed

Algorithm Walkthrough

  1. Initialize binary search bounds: Set left = 1 and right = 10^7, which is guaranteed by the problem statement to be a sufficient upper bound.
  2. Binary search loop: While left <= right, compute the mid-point speed mid = (left + right) // 2. This represents the candidate speed.
  3. Compute travel time at current speed: For each train ride, compute time = dist[i] / mid. For all trains except the last one, round the time up to the nearest integer. Sum all times to get the total travel time.
  4. Check feasibility: If the total travel time is less than or equal to hour, this speed is feasible. Move the right bound to mid - 1 to try a smaller speed. Otherwise, move left to mid + 1 to try a larger speed.
  5. Return result: After the binary search finishes, if a feasible speed was found, return it. If no speed satisfies the condition, return -1.

Why it works: The total travel time decreases monotonically as speed increases. By performing binary search, we efficiently narrow down the minimum speed that satisfies the total time constraint.

Python Solution

from typing import List
import math

class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        left, right = 1, 10**7
        result = -1
        
        while left <= right:
            mid = (left + right) // 2
            total_time = 0.0
            
            for i in range(len(dist)):
                t = dist[i] / mid
                if i != len(dist) - 1:
                    total_time += math.ceil(t)
                else:
                    total_time += t
            
            if total_time <= hour:
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result

This implementation initializes binary search bounds, iterates through possible speeds, computes the travel time rounding up for all but the last train, and updates the search bounds accordingly. The final result is either the minimum feasible speed or -1 if no speed works.

Go Solution

import (
    "math"
)

func minSpeedOnTime(dist []int, hour float64) int {
    left, right := 1, 10000000
    result := -1
    
    for left <= right {
        mid := (left + right) / 2
        totalTime := 0.0
        
        for i := 0; i < len(dist); i++ {
            t := float64(dist[i]) / float64(mid)
            if i != len(dist)-1 {
                totalTime += math.Ceil(t)
            } else {
                totalTime += t
            }
        }
        
        if totalTime <= hour {
            result = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    
    return result
}

Go-specific differences include explicit type conversion for division between integers and floating-point numbers, and using math.Ceil for rounding up.

Worked Examples

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

Binary search tests speeds starting from mid values. At speed 1, travel times are [1, 3, 2] rounded as [1, 3, 2]. Total = 6, which matches hour. Minimum speed = 1.

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

Binary search finds minimum speed 3. Travel times: [1/3, 3/3, 2/3] rounded as [1, 1, 0.6667]. Total ≈ 2.6667 ≤ 2.7.

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

Even at max speed 10^7, total travel time exceeds 1.9. Return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n * log(MaxSpeed)) Binary search on speed (log(MaxSpeed)) and compute total time for each speed (n)
Space O(1) Only a few variables are used for computation

The approach is efficient because it avoids checking every speed individually, relying on the monotonic relationship between speed and total travel time.

Test Cases

# Provided examples
assert Solution().minSpeedOnTime([1,3,2], 6) == 1  # Minimum speed 1
assert Solution().minSpeedOnTime([1,3,2], 2.7) == 3  # Minimum speed 3
assert Solution().minSpeedOnTime([1,3,2], 1.9) == -1  # Impossible to arrive on time

# Boundary cases
assert Solution().minSpeedOnTime([1], 1) == 1  # Single train, exact hour
assert Solution().minSpeedOnTime([1], 0.5) == -1  # Single train, hour too small
assert Solution().minSpeedOnTime([100000], 100000) == 1  # Large distance with sufficient hour

# Stress cases
assert Solution().minSpeedOnTime([100000]*10, 100001.5) == 1  # Multiple large distances
Test Why
[1,3,2], 6 Normal case, arrival exactly at hour
[1,3,2], 2.7 Requires rounding and precise floating point calculation
[1,3,2], 1.9 Impossible due to integer departure rule
[1], 1 Single element edge case
[1], 0.5 Single element impossible case
[100000], 100000 Large distance, minimal speed feasible
[100000]*10, 100001.5 Stress test with repeated large distances

Edge Cases

The first important edge case is when hour is smaller than the number of trains, excluding the last train. This guarantees impossibility because even if all trains traveled at infinite speed, the waiting times alone would exceed hour. The solution handles this naturally in the binary search.

The second edge case is when the last train has a fractional travel time. Only the last train can have fractional hours without rounding, and we carefully handle this by not applying ceil to the last segment.

The third edge case is large input sizes, such as maximum dist[i] and n. Our algorithm scales linearly with n per iteration of binary search and logarithmically with the maximum possible speed, which ensures performance even for the largest constraints.

This implementation correctly handles floating-point arithmetic and rounding, avoids integer overflow by using appropriate data types, and efficiently finds the minimum feasible speed or returns -1.