The problem
Cars drive toward a finish line on a single-lane road. Each car has a starting position and speed. A car cannot pass the one in front; if it catches up, they move together as a fleet at the slower speed. How many fleets reach the finish?
Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3] Output: 3
Picture it
Picture the cars on the road and work from the car nearest the finish backwards. For each car compute arrival time = remaining distance ÷ speed. If a car behind would arrive sooner than (or at the same time as) the fleet in front of it, it catches up and joins that fleet. If it would arrive later, it can never catch up, so it starts a new fleet.
How to recognise it
- Things move along one line and cannot overtake, so what happens to an item depends only on the items ahead of it.
- Each item has a single number that decides its fate: here the time it would take to reach the target alone,
(target - pos) / spd. - Processing items in order of position (front to back) turns "who blocks whom" into a comparison with the group just ahead. That is a sort plus a stack (or a running maximum).
- Up to 10^5 cars, so comparing every car with every car ahead of it is too slow.
Start with brute force
Compute each car's solo arrival time. A car leads its own fleet exactly when it would arrive later than every car in front of it; otherwise it catches some car ahead and joins that car's fleet. Count the leaders.
def car_fleet_brute(target, position, speed):
n = len(position)
times = [(target - position[i]) / speed[i] for i in range(n)]
fleets = 0
for i in range(n):
# car i leads a fleet if it is slower to arrive than every car ahead
if all(times[i] > times[j] for j in range(n) if position[j] > position[i]):
fleets += 1
return fleets
Time is O(n²) because each car looks at every other car, and space is O(n) for the times. For n = 10^5 that is about 10^10 comparisons.
From brute force to the idea
- Find the waste. Each car only needs the largest arrival time among the cars in front of it, but the brute force recomputes that maximum from scratch for every car.
- Sort front first.
sorted(zip(position, speed), reverse=True)lists the car nearest the target first. Now "the cars in front" are exactly the cars already processed. - A fleet arrives when its slowest leader does. Cars that catch up slow down, so a fleet reaches the target at its leading car's solo time.
- Compare with the fleet just ahead. If a car's time
tis greater thanfleets[-1], it can never catch that fleet, so it starts a new one and its time is pushed. Otherwise it catches up at or before the target and merges, so nothing is pushed. - The answer is the number of fleets. Each pushed time is one fleet, so return
len(fleets).
The times in fleets only ever increase, so the list never pops: fleets[-1] is simply the running maximum. A counter plus one variable would work just as well.
This is the key idea: sort by position from the front, then a car starts a new fleet only if it is slower than the slowest fleet ahead.
The key idea
Sort by position (closest to the finish first) and compare arrival times; a new fleet starts only when a car is slower to arrive than the fleet ahead.
Python solution
def car_fleet(target, position, speed):
cars = sorted(zip(position, speed), reverse=True) # front first
fleets = [] # arrival time of each fleet
for pos, spd in cars:
t = (target - pos) / spd
if not fleets or t > fleets[-1]:
fleets.append(t) # too slow to catch up: new fleet
# else: catches the fleet ahead and joins it
return len(fleets)In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every car checks every car ahead | O(n): the arrival times |
| Sort + fleet list (shown code) | O(n log n): the sort dominates; the loop is O(n) | O(n): the sorted pairs and the fleet times |
Edge cases
- One car: returns 1.
- Catching up exactly at the target (target 10, positions
[0, 5], speeds[2, 1]): both take 5 hours,t > fleets[-1]is false, so they count as one fleet, as LeetCode requires. - Everyone catches the front car (target 100, positions
[0, 2, 4], speeds[4, 2, 1]): returns 1. - The example returns 3, with fleets of 2, 2 and 1 cars.
- Floating-point times: with targets and speeds up to 10^6, two different exact times differ by far more than the rounding error of a division, so floats are safe here. Comparing
(target - p1) * s2with(target - p2) * s1avoids floats entirely.
Common mistakes
- Sorting by speed or by time instead of by position. Blocking depends on who is in front.
- Sorting from the back (ascending position). The comparison then checks a car against the cars behind it, so two equal-speed cars, which never meet, are wrongly merged.
- Using
>=to start a new fleet, which splits cars that arrive at the same moment. - Simulating the cars hour by hour. Times are fractions, so a step-by-step simulation is both slow and inexact.
Return the number of cars in each fleet, listed from the fleet that arrives first to the last. For the example the answer is [2, 2, 1]. Describe your approach, then write it if you like.
Compare with our answer
Process cars front first exactly as before. When a car starts a new fleet, append a size of 1; when it merges, add 1 to the last size.
def fleet_sizes(target, position, speed):
cars = sorted(zip(position, speed), reverse=True)
times, sizes = [], []
for pos, spd in cars:
t = (target - pos) / spd
if not times or t > times[-1]:
times.append(t)
sizes.append(1)
else:
sizes[-1] += 1 # joins the fleet just ahead
return sizes
The sizes add up to n, and len(sizes) equals the shown code's answer. Time O(n log n), space O(n).
A strong answer mentions: that a merging car always joins the most recent fleet (not an earlier one), why the front fleet arrives first, and checking that the sizes sum to the number of cars.
1. Runners on a narrow track cannot pass; a faster runner who catches up must jog behind. You must count the groups that cross the line. Which approach fits best?
This is Car Fleet with runners: blocking depends on order on the track, and arrival time decides merging. Speeds alone ignore distance, and a step simulation is slow and misses catches between steps.
2. Why is the shown code O(n log n) rather than O(n)?
The loop does O(1) work per car, so the sort dominates. List appends are O(1) amortised, and each car looks only at fleets[-1], not at every fleet.
3. A learner sorts with sorted(zip(position, speed)), back car first, and keeps the rest unchanged. Which input now gives a wrong count?
Back first, the car at 0 (10 hours) is pushed, then the car at 5 (5 hours) is not slower, so it is wrongly merged and the answer is 1. In the other inputs the cars really do merge or there is only one car, so the order does not change the count.
Score 60% or more and the lesson is marked complete.