Coding · Binary search
Minimum Speed to Arrive on Time
- Reported once
- Medium
- SDE (on-campus, 2021)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You take n trains in order, all at the same integer speed in km per hour, and dist[i] is the length of the i-th ride. A train departs only on a whole hour, so after each ride except the last you wait for the next whole hour. Given the allowed total time hour (at most two decimal places), return the smallest positive integer speed that arrives in time, or -1 if none does. For dist = [2,4,7,3] and hour = 6.5 the answer is 4. There can be 100,000 rides, each at most 100,000 km, and hour is at most 100.
Restated in our own words, not a quote from PhonePe or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: must the speed be an integer, and is it the same for every train? Is the waiting only between rides, so the last ride ends the moment it arrives? Are distances positive? Does hour have at most two decimals? Is there an upper limit on the answer, and what is returned when no speed works?
I would assume integer speed shared by all trains, no waiting after the last ride, positive distances, at least one ride, and -1 when impossible. Because hour is a decimal, I will convert it to whole hundredths so floating-point rounding never decides a comparison.
Brute force
Say the obvious answer and why it is too slow.
Try speeds 1, 2, 3 and so on. For each speed, add up ceil(dist[i] / speed) for every ride except the last, add dist[last] / speed, and compare with hour. The first speed that fits is the answer.
Each check costs O(n), and the answer can be huge: a last ride of 100,000 km with only 0.01 hours left for it needs a speed of 10 million. So the loop can run ten million times over a hundred thousand rides, about 10^12 operations, far beyond any time limit. Most of those speeds are obviously too slow or just as good as their neighbors, so the work is wasted.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n · V)
- Time
- O(n log V)
- Space
- O(1)
The pattern is binary search on the answer. The question "does speed s arrive in time?" is monotone: raising the speed never makes any ceiling term bigger and always makes the last ride shorter, so total time never goes up as speed goes up. The answers over s = 1, 2, 3 and so on look like no, no, no, yes, yes, yes, and I am looking for the first yes. Checking a single speed is a linear scan, so the search costs O(n log V) with V the largest speed tried.
Bounds come from reasoning, not guessing. Each of the first n - 1 rides takes at least one full hour, and the last takes some positive time, so if hour is at most n - 1 the answer is -1. Otherwise, any speed at least the longest ride makes every earlier ride take exactly one hour, which leaves hour - (n - 1) for the last ride, so speed ceil(dist[last] / that) also suffices. Take the larger of the two as the upper bound; it is always feasible, so no further -1 check is needed.
The precision trap: hour like 2.01 is not exact in binary. I work in hundredths. Waiting time is an integer number of hours times 100, and the last ride fits if dist[last] · 100 is at most the remaining hundredths times speed. Everything stays an integer comparison. Explained aloud: I am not searching the array, I am searching the space of speeds, because each guess can be tested in a single pass.
Walk it through
A dry run on the example, step by step.
| Step | low..high | mid | Waits (hours) | Arrives in time? |
|---|---|---|---|---|
| start | 1..7 | - | - | - |
| 1 | 1..7 | 4 | 1+1+2 = 4 | yes, high = 4 |
| 2 | 1..4 | 2 | 1+2+4 = 7 | no, low = 3 |
| 3 | 3..4 | 3 | 1+2+3 = 6 | no, low = 4 |
| done | 4..4 | - | - | answer 4 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take dist = [2,4,7,3] and hour = 6.5, which is 650 hundredths. The first three rides take at least 3 hours, leaving at most 3.5 hours for the last one. The upper bound is the larger of 7 (the longest ride) and ceil(300 / 350) = 1, so 7. Search from 1 to 7.
Mid 4: the first three rides use 1 + 1 + 2 = 4 hours, leaving 2.5 for the last ride of 3 km at speed 4, which fits; high becomes 4. Mid 2: the waits are 1 + 2 + 4 = 7 hours, already over 6.5, so low becomes 3. Mid 3: waits are 1 + 2 + 3 = 6 hours, leaving 0.5, but 3 km at speed 3 takes 1 hour, so it fails and low becomes 4. Low meets high at 4, as the table shows.
The code
Runnable JavaScript, checked against test cases.
function minSpeedOnTime(dist, hour) {
const rides = dist.length;
const limit = Math.round(hour * 100);
const guaranteed = (rides - 1) * 100;
if (limit <= guaranteed) return -1;
const lastRide = dist[rides - 1];
const arrivesInTime = (speed) => {
let used = 0;
for (let i = 0; i < rides - 1; i++) {
used += Math.ceil(dist[i] / speed) * 100;
}
const remaining = limit - used;
return remaining > 0 && lastRide * 100 <= remaining * speed;
};
const longest = dist.reduce((a, b) => Math.max(a, b), 0);
let low = 1;
let high = Math.max(longest, Math.ceil((lastRide * 100) / (limit - guaranteed)));
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (arrivesInTime(mid)) high = mid;
else low = mid + 1;
}
return low;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
If hour is at most n - 1, the guard returns -1 before any search. That includes hour exactly equal to n - 1, because the last ride needs time greater than zero. With one ride there is no waiting, the guaranteed time is 0, and the answer is ceil(dist / hour); for [5] and hour 0.5 the code returns 10.
A speed of 1 is the minimum, so the search never goes below it. When hour leaves only 0.01 hours for the last ride, the answer can be in the millions, for example [1,1,100000] with hour 2.01 gives 10,000,000, and the upper bound computed from the remaining time covers it. The comparison inside the check is at most, not strictly less, so arriving exactly on time counts. The code assumes at least one ride.
Follow-ups to expect
Where the interviewer pushes next.
- What changes if speeds may be any positive real number instead of an integer?
- How would the answer change if you also had to wait for a whole hour after the last ride?
- Can you prove the arrives-in-time check is monotone in the speed?
- How would you cut the number of binary search steps by tightening the bounds further?
- How would you return the minimum speed when each train also has its own maximum speed?
Where candidates slip
The mistakes this problem punishes.
Applying the ceiling to the last ride too, which models waiting after arrival and gives a speed that is too high. This is a classic mistake on this problem.
Others: comparing floating-point sums directly to hour so a case that lands exactly on the limit flips; testing hour less than n instead of hour at most n - 1; using a strict less-than so exact arrival is rejected; hard-coding an upper bound of ten million without the impossible case; returning mid rather than low when the loop ends; and writing the update as high = mid - 1 in a search that keeps the feasible candidate, which skips the real answer. Forgetting that speed must be an integer, and returning a decimal, is another frequent slip.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.