Cars are driving along a one-lane road toward a finish line at position target. Car i starts at position[i] and drives at speed[i]. Cars cannot overtake. When a faster car catches up with a slower car ahead of it, it slows down and they drive together from then on, bumper to bumper. A group of cars driving together is called a fleet. A single car on its own also counts as a fleet.
Read it as "the distance left for car i, divided by its speed". A car 2 units away going at speed 2 needs 1 unit of time.
Fact 2. A car only cares about the fleet directly in front of it. If a car would reach the finish sooner than the fleet ahead of it, it must catch that fleet on the way, and then it is stuck behind it. If it would arrive later, it can never catch up, so it forms its own fleet.
So the real question is: walking from the car nearest the finish backwards, how many times does a car arrive later than every car in front of it?
Simulate the road. Move every car forward by a tiny time step, merge any cars that touch, and repeat until everyone has finished.
The number of steps depends on how far the finish line is and how small the time step is, not on the number of cars. A distant finish line means millions of steps, each one doing work for every car. It is also easy to get wrong, because two cars can meet between two time steps.
The waste in one sentence: it simulates every moment of the drive, when all we need is each car's arrival time and the order of the cars on the road.
Sort the cars by position, nearest to the finish first.
Walk through them in that order, keeping a stack of the arrival times of the fleets found so far.
For each car, work out its arrival time on its own.
If it is later than the fleet just ahead, this car can never catch up. It leads a new fleet. Push its time.
Otherwise it catches that fleet and joins it. Do nothing. The fleet still arrives at the slower front car's time.
Imagine standing at the finish with a stopwatch. You look at the nearest car and work out "alone, it arrives in 5 minutes". You write down 5. The car behind it would arrive alone in 3 minutes. But it cannot pass the car in front, so it gets stuck and arrives at 5 too. You do not write anything new. You only write a new time when a car would arrive later than the one ahead, because that car never catches up.
The times you write down always increase as you walk backwards. Anything smaller gets swallowed into the fleet ahead. That is a monotonic stack again.
(1) Pair and sort.zip(position, speed) pairs the first position with the first speed, the second with the second, and so on, giving pairs like (10, 2). sorted(..., reverse=True) sorts these pairs by position from largest to smallest. Python compares pairs by their first item, so this sorts by position. The car nearest the finish comes first.
In TypeScript, map builds the pairs and sort orders them. The comparison (a, b) => b[0] - a[0] sorts by position, largest first. Without it, JavaScript would sort the pairs as text, which gives the wrong order.
(2) The stack of fleet arrival times.
(3) Walk the cars from the front of the road to the back.
(4) This car's arrival time if it were alone. This must be decimal division. In Python that is /, never //. The car at position 8 with speed 4 needs \frac{4}{4} = 1.0. A car at position 10 with speed 4 would need \frac{2}{4} = 0.5. With //, that 0.5 would become 0, the car would look like it was already at the finish, and the comparisons in line (5) would go wrong. In TypeScript, / already gives decimals.
(5) Does this car arrive later than the fleet just ahead?fleets[-1] is the arrival time of the fleet directly in front. If the stack is empty, this is the first car, so it is a new fleet.
We only compare with the last fleet, not all of them. If a car cannot catch the fleet just ahead, it certainly cannot catch any fleet further ahead, because those arrive even sooner.
We use >, not >=. A car that would arrive at exactly the same time as the fleet ahead catches it right at the finish line, and the problem counts that as one fleet.
(6) A new fleet. Push its arrival time. Every car behind will compare against this one.
If the check in line (5) fails, nothing happens. The car joins the fleet ahead, and that fleet's arrival time does not change. A fleet moves at the speed of its slowest, front car.
(7) The number of fleets is the number of times we pushed.
target = 12. After sorting by position, largest first:
Position
Speed
Time alone
Compared with fleet ahead
Result
fleets after
10
2
(12 − 10) / 2 = 1.0
no fleet yet
new fleet
[1.0]
8
4
(12 − 8) / 4 = 1.0
1.0 is not > 1.0
joins
[1.0]
5
1
(12 − 5) / 1 = 7.0
7.0 > 1.0
new fleet
[1.0, 7.0]
3
3
(12 − 3) / 3 = 3.0
3.0 is not > 7.0
joins
[1.0, 7.0]
0
1
(12 − 0) / 1 = 12.0
12.0 > 7.0
new fleet
[1.0, 7.0, 12.0]
The answer is 3.
The car at position 3 is the interesting one. Alone, it would finish at time 3, which is fast. But the car ahead at position 5 finishes at time 7, so the faster car catches it on the way and is stuck behind it. Being fast does not make it a separate fleet.
Time. Sorting n cars takes O(n \log n). The loop then visits each car once and does constant work. So the total is O(n \log n) + O(n) = O(n \log n). The sort is not a convenience here. Without the order of the cars on the road, the question cannot be answered.
Space. The sorted list of pairs holds n pairs, and the stack can hold up to n times if every car forms its own fleet. So the space is O(n).
Comparing decimals can go wrong in real programs, because computers store most decimals slightly inexactly. Two arrival times that should be equal might differ in the last digit, and the > in line (5) would give the wrong answer.
You can compare two fractions without ever dividing, by cross-multiplying. For positive b and d:
\frac{a}{b} > \frac{c}{d} \quad\text{exactly when}\quad a \times d > c \times b
Read it as "a over b is bigger than c over d exactly when a times d is bigger than c times b". Multiplying both sides by b \times d removes both fractions, and since b and d are positive, the direction of > does not change. Mentioning this without being asked is a strong signal.
No. Line (5) only ever reads the last time. So one variable for the last fleet's time, plus a counter, would do the same job in O(1) extra memory. The list is kept here because it makes the "always increasing" shape easy to see. If an interviewer asks, say that you noticed. It shows you understood the algorithm, not just the chapter it was filed under.
"Why sort by position?" Because only the order along the road tells you which car is in front of which.
"Why compare only with the last fleet?" Fleets further ahead arrive even sooner, so failing to catch the nearest one means failing to catch any.
"Why decimal division?" Whole-number division turns small arrival times into 0 and breaks the comparisons. Then offer cross-multiplying.
"Do you need the stack?" No, one variable is enough.
"What if cars could overtake?" Then there are no fleets, and the answer is just the number of cars. The no-overtaking rule creates the whole problem.
One thing to volunteer: say the reduction in one sentence before coding. "Sort from the finish backwards, compute each car's time alone, and count how many times the time goes up."