Abstract / Summary

Find the slowest speed to reach a destination on time given distance and time constraints.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 48% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method minSpeedOnTime. The method receives a list of integer distances and a floating-point time limit, and it returns the smallest integer speed that allows traveling the entire route within the given hour. The algorithm combines a helper function that computes the total travel time for a candidate speed with a binary search over the feasible speed range.

Core Logic

Time Computation

A nested function time(speed) iterates over each segment distance, accumulating the travel time. For each segment the elapsed time is rounded up to the next integer before adding the fractional travel time of the current segment. This reflects the requirement that all but the last segment must be completed in whole hours. The function returns the total time needed when traveling at the supplied speed.

def time(speed):
    result = 0
    for d in dist:
        result = ceil(result) + d / speed
    return result

Feasibility Check

Before entering the binary search, the code verifies whether the maximum considered speed (10**7) can satisfy the time constraint. If even this speed yields a travel time larger than the allowed hour, the method returns -1, indicating impossibility.

if time(right) > hour:
    return -1

Binary Search

The search interval is initialized with left = 1 and right = 10**7. The loop continues until left equals right. At each iteration the midpoint mid is computed using integer division. The time function evaluates whether mid is sufficient. If the travel time exceeds the limit, the lower bound is moved just above mid; otherwise, the upper bound is set to mid. When the loop terminates, left (or right) holds the minimal speed that meets the requirement.

while left != right:
    mid = (left + right) // 2
    if time(mid) > hour:
        left = mid + 1
    else:
        right = mid
return left

Edge Cases Handled

The algorithm explicitly addresses the scenario where no feasible speed exists within the predefined search range. By testing the upper bound before the binary search, it ensures that an early exit occurs when the problem is unsolvable, returning -1.

Another subtle edge case involves the rounding behavior for intermediate segments. The use of ceil(result) guarantees that any fractional time accumulated from previous segments does not affect the integer hour requirement for the next segment. This correctly handles cases where a segment finishes exactly at an integer hour, as ceil will leave the value unchanged, preserving the intended timing semantics.

The method also accommodates the situation where the required speed is exactly 1. Since the lower bound starts at 1, the binary search can converge to this minimal value without additional special handling.

Floating-point precision is managed by performing division d / speed using Python’s native float arithmetic, which is sufficient for the problem constraints and avoids integer division pitfalls.

Performance Optimizations

The most notable optimization is the use of binary search over a bounded integer interval rather than a linear scan of possible speeds. By halving the search space each iteration, the algorithm quickly converges to the minimal feasible speed.

The helper time function avoids unnecessary data structures; it works directly with the input list and a simple accumulator. The call to ceil is applied only to the current accumulated time, not to each segment individually, reducing the number of rounding operations.

The early feasibility check prevents the binary search from executing when the answer is known to be impossible, saving the cost of multiple time evaluations.

Overall, the combination of a tight search interval, minimal per-iteration work, and an upfront impossibility test yields an efficient solution that scales well with the size of the distance list and the magnitude of the speed range.

Imagine a little robot trying to travel through several different towns. Each town is a specific distance away, and the robot needs to finish the whole trip before a certain amount of time passes. If the robot goes very fast, it finishes quickly, but if it goes too slowly, it misses its deadline.

To solve this, the code thinks about how fast the robot is moving. It starts by picking a speed right in the middle between the slowest possible speed and a super fast speed. Then, it calculates how much time that would take. If the total time is too long, the robot needs to go faster, so it ignores all the slower speeds and picks a new middle point from the faster range. If the time is just right or even faster than the goal, it knows it could maybe go a bit slower to save energy, so it keeps that speed as a possibility and looks at the slower range instead.

It keeps chopping the range of speeds in half over and over again like a game of guessing a number. This happens until the range becomes so small that there is only one speed left that works. This is a very efficient way for the computer to find the perfect speed without checking every single possibility one by one.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python		TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++	JS	Java		Go	Python	Rust	TS
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	suxrobGM				C#
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality