Car Fleet
Cars at given positions and speeds drive toward a target; a faster car catching a slower one joins its fleet at the slower speed. Return the number of fleets that arrive.
Open on LeetCode ↗Intuition
It feels natural to walk the cars from the back of the line forward, in the order they're given, but a car can only be blocked by one ahead of it toward the target — so you must process from closest-to-target backwards, or the fleet a car might join hasn't been decided yet. Compute each car's solo arrival time, (target - position) / speed, using true division; integer division truncates two close arrival times into looking equal and silently merges fleets that should stay separate. A car merges into the fleet ahead exactly when its arrival time is no later than that fleet's, so sweep with a running maximum: any time that exceeds the current maximum starts a new fleet.
Sort by position descending and compute each car's arrival time. A car catches the fleet ahead if its time is no greater than the running maximum; otherwise it leads a new fleet. Processing from the front backwards means the blocking car is always already known.
Approach
Reduce each car to a single number
Positions and speeds together are awkward, but arrival time (target - position) / speed captures everything that matters. Two cars are in the same fleet exactly when the one behind would otherwise arrive no later than the one ahead.
Sort by position descending
Process from the car nearest the target backwards. Only cars ahead can block you, so this order means the fleet you might join has already been decided by the time you are considered.
Sweep with a running max
Keep slowest, the arrival time of the fleet currently ahead. If the next car's time is greater, it never catches up — it forms a new fleet, so increment the count and set slowest to its time. Otherwise it merges and changes nothing. Sorting dominates at O(n log n), with O(n) space; a stack is a common alternative formulation, but the running max is the same idea with less machinery.
Solution & live demo
Common pitfalls
Sorting by position ascending
cars = sorted(zip(position, speed))
cars = sorted(zip(position, speed), reverse=True)
A car can only be blocked by one ahead of it, so those must be processed first. Ascending order asks about blockers that haven't been examined yet.
Comparing speeds rather than arrival times
if s < slowest_speed: fleets += 1
t = (target - p) / s if t > slowest:
A faster car far behind may still never catch up before the target. Only the time to reach the destination decides whether a merge actually happens within the road's length.
Using >= for the new-fleet test
if t >= slowest:
if t > slowest:
Equal arrival times mean the cars reach the target together, which counts as one fleet. The >= version splits them and overcounts on ties.
Edge cases
It is its own fleet, so the answer is 1.
None ever catches another, so every car is its own fleet.
They arrive together and count as one fleet, so the comparison must be strict > for a new fleet.
Arrival times need to be floats — truncating can merge fleets that should stay separate.