Car Fleet (LeetCode 853): Sort by Position, Then Think in Arrival Times
3 views
Car Fleet is a medium problem that looks like a physics simulation but collapses into a few lines once you change how you look at it. There are n cars on a one-lane road heading to a target. Each car has a starting position and a speed. A faster car cannot pass a slower one; when it catches up, they move together as a fleet at the slower speed. Count how many fleets arrive at the target.
Why simulation is the wrong path
You could step time forward and merge cars, but time is continuous and speeds are arbitrary, so the simulation is messy and slow. Interviewers want to see you avoid it.
Key insight 1: process cars from closest to the target
A car can only be blocked by cars ahead of it. So sort cars by position in descending order and walk from the front of the road backward.
Key insight 2: compare arrival times, not positions
For each car, compute the time it would need to reach the target alone: (target - position) / speed. Now walk from front to back:
- If a car's arrival time is greater than the current fleet's arrival time ahead of it, it can never catch up, so it starts a new fleet.
- If its time is less than or equal, it catches the fleet ahead before (or exactly at) the target, so it merges and takes on that fleet's arrival time.
Python
def car_fleet(target, position, speed):
cars = sorted(zip(position, speed), reverse=True)
fleets = 0
slowest = 0.0
for pos, spd in cars:
t = (target - pos) / spd
if t > slowest:
fleets += 1
slowest = t
return fleets
Time is O(n log n) for sorting, space O(n) for the pairs.
The stack version
Many solutions push arrival times onto a stack and pop when a car merges. That is the same idea; the single variable above is enough because only the most recent fleet's time matters. It is still worth mentioning, since interviewers who expect the stack pattern will recognize it.
Edge cases to raise
- Cars that meet exactly at the target count as one fleet, which is why the merge condition uses less than or equal.
- A single car is one fleet.
- Floating point: times are fractions. Comparing with floats is usually fine here, but you can compare cross-multiplied integers ((target - p1) * s2 versus (target - p2) * s1) if you want to be exact. Saying this shows care.
How to explain it in an interview
Start by stating that order matters only from the front, then introduce arrival time as the single number that summarizes each car. Walk through the sample: target 12, positions [10, 8, 0, 5, 3], speeds [2, 4, 1, 1, 3]. Times sorted by position are 1, 1, 7, 3, 12, giving fleets at 1, 7, and 12, so the answer is 3.
Related problems
The same "sort, then sweep with a running summary" idea appears in Car Fleet II, meeting room scheduling, and many greedy interval problems.
Support during the interview
If you tend to freeze when a problem looks like a simulation, Linkjob AI (https://linkjob.ai) provides real-time help during live job interviews and technical interviews, offering hints and structure while you reason it out in your own words.