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.
- n == position.length == speed.length
- 1 <= n <= 10⁵
- 0 < target <= 10⁶
- 0 <= position[i] < target
- All the values of position are unique.
- 0 < speed[i] <= 10⁶
Intuition
Car fleet leetcode problem 853 asks how many groups of cars arrive at a destination together. A faster car that catches a slower one ahead cannot pass — it slows down and joins that car's fleet permanently.
Positions and speeds do not answer this directly. The quantity that does is time to reach the target, computed as (target − position) / speed. Once every car is expressed as an arrival time, the geometry disappears.
The key insight concerns which car controls a fleet. A car catches up only to cars ahead of it, never behind, so processing must go from the destination backwards:
- Sort cars by position descending, then walk from the car closest to the target toward the furthest.
The car nearest the target is a fleet leader by definition — nothing ahead can slow it. For every car behind it, compare arrival times.
If a car's time is less than or equal to the current leader's, it would arrive sooner, meaning it catches up and merges into that fleet. Its own time is then irrelevant, because it travels at the leader's pace.
If its time is greater, it can never catch up and becomes a new fleet leader for the cars behind it.
So the count is the number of times the arrival time increases as you walk backwards from the target. A stack is often used to hold the leaders, but a single variable tracking the current leader's time is enough.
The comparison must be <=, not <. Cars arriving at exactly the same time are in the same fleet, and using strict inequality overcounts.
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
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n log n) time and O(n) space.
Convert to arrival times
Compute (target - position) / speed for each car. Positions and speeds do not compare directly, but arrival times do — this substitution removes the geometry entirely.
Sort by position descending
A car can only be blocked by cars ahead of it, so process from the destination backwards. The car nearest the target is a fleet leader by definition.
Compare each car to the current leader
Walking backwards, compare each car's arrival time against the leader's. This single comparison decides whether the car merges or starts a fleet.
Merge when the time is not greater
A time less than or equal to the leader's means the car catches up and joins that fleet. Its own time then stops mattering, since it travels at the leader's pace.
Start a new fleet otherwise
A greater arrival time means the car can never catch up. It becomes the new leader for everything behind it, and the fleet count increases.
Use non-strict comparison
The test must be <=, not <. Cars arriving at exactly the same moment belong to one fleet, and strict inequality overcounts them as two.
Cost of the approach
Sorting dominates at O(n log n) time, with the backward scan O(n). Space is O(n) for the sorted pairs — a single leader variable replaces the usual stack.
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.