Car Fleet
Cars on a one-lane road can't overtake, so fast cars bunch up behind slow ones. Count how many groups arrive at the finish.
- Sort, then stack to merge groups
- Monotonic stack
Before this, know: Sorting an array, What a stack is (push, pop, peek), Time = distance ÷ speed
n cars drive along a one-lane road toward the same finish line at mile
target. Car i starts at mile position[i] and drives at speed[i] miles
per hour. Because it’s one lane, a car can never overtake the car in front.
If a faster car catches up with a slower one, it slows down and they drive
together, bumper to bumper.
A group of cars driving together is called a fleet. A single car on its own is also a fleet. If a car catches up with a fleet exactly at the finish line, it still counts as part of that fleet. Return how many fleets arrive.
LeetCode’s example: target = 12, position = [10, 8, 0, 5, 3],
speed = [2, 4, 1, 1, 3]. We’ll call the cars A to E, in input order:
Rules that matter: all positions are different, every car starts before the target, and there can be up to 100,000 cars.
Two ideas make this problem click.
1. Think in arrival times, not speeds. If nothing were in the way, car i
would reach the target after time = (target − position) ÷ speed hours. Car B
at mile 8 with speed 4 needs (12 − 8) ÷ 4 = 1 hour. Car A at mile 10 with speed
2 also needs (12 − 10) ÷ 2 = 1 hour.
2. A car behind catches the car ahead if it would arrive at the same time or sooner. B starts behind A but would arrive no later than A, so B must have caught A somewhere on the road (or at the line). Since B can’t pass, they arrive together, at A’s time.
Here is the real motion of LeetCode’s example, worked out minute by minute. Each line is a car’s position over time. When a faster car catches a slower one, its line bends and merges with the slower car’s line:
Pause and think
X needs (10 − 6) ÷ 2 = 2 hours. Y needs (10 − 2) ÷ 4 = 2 hours too. Y would arrive at the same moment as X, so it catches X exactly at the line. That counts as catching up: one fleet.
A car leads its own fleet if there is no car ahead of it that it would catch. So for each car, look at every other car: is there one ahead of it (bigger position) whose time is the same or longer? If yes, our car catches it and is just a follower. If no, our car is the front of a fleet. Count the leaders.
Brute force: check every car ahead
target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
- checks so far
- 0
- fleets
- 0
- Car i
- Car ahead it catches
- Leads a fleet
- Follows someone
Car A alone would take 1h. Is there a car ahead of it that arrives at the same time or later? Then A catches it.
Which line is running?
function carFleet(target, position, speed) { const n = position.length; let fleets = 0; for (let i = 0; i < n; i++) {Running now: const time = (target - position[i]) / speed[i]; let catchesUp = false; for (let j = 0; j < n; j++) { const ahead = position[j] > position[i]; if (ahead && (target - position[j]) / speed[j] >= time) { catchesUp = true; // car i reaches car j before the target break; } } if (!catchesUp) fleets++; // nobody to catch: car i leads a fleet } return fleets;}Brute force: check every car ahead
function carFleet(target, position, speed) { const n = position.length; let fleets = 0; for (let i = 0; i < n; i++) { const time = (target - position[i]) / speed[i]; let catchesUp = false; for (let j = 0; j < n; j++) { const ahead = position[j] > position[i]; if (ahead && (target - position[j]) / speed[j] >= time) { catchesUp = true; // car i reaches car j before the target break; } } if (!catchesUp) fleets++; // nobody to catch: car i leads a fleet } return fleets;}def car_fleet(target, position, speed): n = len(position) fleets = 0 for i in range(n): time = (target - position[i]) / speed[i] catches_up = False for j in range(n): ahead = position[j] > position[i] if ahead and (target - position[j]) / speed[j] >= time: catches_up = True # car i reaches car j before the target break if not catches_up: fleets += 1 # nobody to catch: car i leads a fleet return fleetsEvery car compares itself with every other car. With 5 cars that’s up to 5 × 5 = 25 checks. With 100,000 cars it’s up to 100,000 × 100,000 = 10,000,000,000 checks. That’s O(n²).
The brute force re-checks the same cars ahead over and over. If we sort the cars so we process them from the front of the road backwards, then by the time we reach a car, every car ahead of it has already been grouped into fleets. And the only fleet it can possibly catch is the one directly ahead of it.
Pattern
Sort, then stack to merge groups
Use it when: items interact only with their neighbours once put in order, and some of them merge into groups (fleets, overlapping intervals, collisions).
Signal words
- “fleet”
- “catch up”
- “cannot pass”
- “merge”
- “how many groups arrive”
Why is a fleet’s arrival time just its front car’s time? Cars behind the front car only catch up to it, they never make it go faster. So the fleet arrives when its front car would have arrived on an empty road. The times on the stack always increase from bottom to top, which makes it a monotonic stack too.
- For every car, compute
time = (target − position) ÷ speed. Keep it paired with the position. - Sort the pairs by position, largest first (closest to the target first).
- Make an empty stack of arrival times, one per fleet.
- For each car in that order: if the stack is empty, or this car’s time is greater than the time on top, push its time: it’s a new fleet. Otherwise it catches the fleet ahead and merges: push nothing.
- Return the stack’s size.
Press Play. The road shows every car; each car gets the colour of its fleet as it’s processed, and the stack on the left grows only when a new fleet is born. The tie at the target edge case shows a car that catches up exactly at the line.
Sort, then stack the fleets
target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
- empty
- order (front first)
- —
- this car's time
- —
- fleet ahead arrives
- —
- fleets
- 0
- Fleet #1
- Fleet #2
- Fleet #3
- Not placed yet
5 cars on a one-lane road heading to mile 12. Nobody can overtake, so a fast car stuck behind a slow one has to slow down.
Which line is running?
Running now: function carFleet(target, position, speed) { // pair each car's position with the time it needs to reach the target const cars = position.map((p, i) => [p, (target - p) / speed[i]]); cars.sort((a, b) => b[0] - a[0]); // closest to the target first const stack = []; // arrival time of each fleet, front fleet at the bottom for (const [, time] of cars) { if (stack.length === 0 || time > stack.at(-1)) { stack.push(time); // slower than the fleet ahead: a new fleet } // otherwise it catches up and joins the fleet ahead } return stack.length;}Sort, then stack
function carFleet(target, position, speed) { // pair each car's position with the time it needs to reach the target const cars = position.map((p, i) => [p, (target - p) / speed[i]]); cars.sort((a, b) => b[0] - a[0]); // closest to the target first const stack = []; // arrival time of each fleet, front fleet at the bottom for (const [, time] of cars) { if (stack.length === 0 || time > stack.at(-1)) { stack.push(time); // slower than the fleet ahead: a new fleet } // otherwise it catches up and joins the fleet ahead } return stack.length;}def car_fleet(target, position, speed): # pair each car's position with the time it needs to reach the target cars = [(p, (target - p) / s) for p, s in zip(position, speed)] cars.sort(reverse=True) # closest to the target first stack = [] # arrival time of each fleet, front fleet at the bottom for _, time in cars: if not stack or time > stack[-1]: stack.append(time) # slower than the fleet ahead: a new fleet # otherwise it catches up and joins the fleet ahead return len(stack)Lines 1–8 match in both languages; after that JavaScript has a closing } and
runs one line ahead.
- Line 1: define the function. (LeetCode wraps it as
var carFleet = function(...), or a method ofclass Solutionin Python.) - Line 3: build a list of pairs
[position, time]. In JavaScript,mapvisits each positionpwith its indexi, sospeed[i]is the same car’s speed. In Python,zip(position, speed)walks both lists side by side./gives a decimal in both languages, which is what we want: times like 2.5 hours are real. - Line 4: sort by position, biggest first. JavaScript’s
sortneeds a compare function:b[0] - a[0]puts the larger position first. Python sorts pairs by their first item, andreverse=Truemakes it largest first. - Line 5: the stack holds one arrival time per fleet. The front fleet is at the bottom.
- Line 6: walk the cars from the front of the road backwards. We only need the
time, so we skip the position (
[, time]in JS,_, timein Python). - Line 7: the decision.
stack.at(-1)/stack[-1]is the arrival time of the fleet directly ahead. If our car needs more time, it never catches up. - Line 8: push its time: a new fleet, led by this car.
- Line 10 (JS) / line 9 (Py): the
elsethat isn’t there. A car that would arrive at the same time or earlier merges into the fleet ahead, which keeps the fleet’s (slower) time. Nothing to do. - Line 12 (JS) / line 10 (Py): one stack entry per fleet.
LeetCode’s example, target = 12. After sorting, the cars come in the order
A (10), B (8), D (5), E (3), C (0).
| car | position | time = (12 − pos) ÷ speed | top of stack | decision | stack after |
|---|---|---|---|---|---|
| A | 10 | 2 ÷ 2 = 1 | (empty) | new fleet | [1] |
| B | 8 | 4 ÷ 4 = 1 | 1 | 1 is not > 1: joins A | [1] |
| D | 5 | 7 ÷ 1 = 7 | 1 | 7 > 1: new fleet | [1, 7] |
| E | 3 | 9 ÷ 3 = 3 | 7 | 3 is not > 7: joins D | [1, 7] |
| C | 0 | 12 ÷ 1 = 12 | 7 | 12 > 7: new fleet | [1, 7, 12] |
| end | return 3 | [1, 7, 12] |
Row B is the “tie” rule in action: B would arrive at exactly the same time as A, so it catches A at the finish line, and that counts as one fleet.
Brute force
Time
O(n²)
Each car checks every other car.
Space
O(1)
Just a counter and a couple of variables.
Sort, then stack
Time
O(n log n)
Sorting costs about n × log₂ n steps (100,000 cars ≈ 1.7 million steps). The loop after it is only n steps.
Space
O(n)
The list of (position, time) pairs, and a stack with up to n fleets.
O(n log n) reads “n log n”: a bit more than straight-line O(n), much less
than O(n²). It’s the usual cost of a good sort. log n is explained in the
week 3 overview.
What to say out loud, in this order:
- Restate the no-overtaking rule and the “catch up at the line counts” rule.
- “Convert each car to its arrival time on an empty road.”
- “A car only cares about the fleet directly ahead, so sort by position, front first.”
- “A car whose time is bigger than the fleet ahead starts a new fleet; otherwise it merges.” Stack of times, answer = its size.
- Cost: O(n log n) for the sort, O(n) space. Dry-run the tie.
Likely follow-up questions:
- “Can you avoid the stack?” Yes: you only ever compare with the top, so a single
variable
slowestAheadand a counter work too. The stack makes the fleets visible. - “When does each fleet arrive?” The values on the stack are exactly those times.
- “Cars can overtake?” Then nobody merges, and the answer is just
n.
Related problems:
- Daily Temperatures (this week): a monotonic stack without the sort.
- Merge Intervals (week 12 of the roadmap): the same “sort, then merge with the last group” idea.
- The week 3 overview has the template.