Car Fleet: Turn a Highway Into a Monotonic Stack
Solve LeetCode Car Fleet with a monotonic stack — sort by position, compute time-to-target, and merge collisions. Full walkthrough, JavaScript, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Car Fleet looks like a physics word problem, and that scares people off. Cars on a one-lane road, no passing, faster cars pile up behind slower ones — how many clumps reach the finish line? Your instinct is to simulate the road tick by tick, and that instinct is a trap.
The whole problem collapses the moment you stop thinking about positions over time and start thinking about one number per car: how long until it reaches the target. Sort the cars from front to back, and a single stack tells you exactly where fleets form.
That reframe — replace a messy simulation with a sorted scan and a stack — is the monotonic-stack pattern, and it powers a whole family of "who blocks whom" problems.
The problem
n cars share a single-lane road heading to a destination target kilometers away. Car i starts at position[i] and drives at constant speed[i]. Cars cannot pass each other — a faster car that catches a slower one is stuck behind it forever, and the two now move together at the slower car's speed. That clump is a fleet (a single car counts as a fleet of one).
Return the number of distinct fleets that arrive at the target.
Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3Two facts do all the work. First, cars only ever interact with the car ahead of them (closer to the target), so front-to-back order matters. Second, a car catches the car ahead if and only if it would reach the target sooner or at the same time when driving freely — because then it must have closed the gap somewhere along the road.
The brute force baseline
Skip the tick-by-tick simulation (fractional collision times and an unbounded number of steps make it both slow and imprecise). A cleaner naive idea: reduce each car to its free-driving arrival time, then for every car check whether any car ahead of it arrives at the same time or later. If one does, this car gets blocked and folds into that fleet; if none do, it leads a fleet of its own.
function carFleet(target, position, speed) {
const cars = position.map((pos, i) => ({
pos,
time: (target - pos) / speed[i],
}));
let fleets = 0;
for (let i = 0; i < cars.length; i++) {
let blocked = false;
for (let j = 0; j < cars.length; j++) {
// A car ahead of i that arrives no sooner blocks car i.
if (cars[j].pos > cars[i].pos && cars[j].time >= cars[i].time) {
blocked = true;
break;
}
}
if (!blocked) fleets++;
}
return fleets;
}This is correct, but the inner loop rescans the whole array for every car — O(n²). On 10⁴ cars that's 100 million comparisons, and it does the same "is anyone ahead of me slower?" work over and over. The fix is to process cars in a fixed order so each one only compares against the fleet directly in front of it.
The key insight: sort by position, stack the arrival times
Line the cars up closest-to-target first (descending position). Walk that order and keep a stack holding the arrival time of each fleet's leader.
Why this works: when you process a car, every car already on the stack is ahead of it on the road. The only thing that can block the current car is the fleet immediately in front of it — the top of the stack. Compare their arrival times:
- Current car's time > top of stack → it arrives later, never catches up, and starts its own new fleet. Push it and move on.
- Current car's time <= top of stack → it would arrive sooner, so it catches the fleet ahead, gets stuck behind it, and merges. Pop it back off.
Because cars are processed front-to-back, the stack stays monotonic and each car is compared exactly once against the leader ahead of it. The inner scan disappears. The number of fleets is simply how many leaders survive on the stack.
The optimal solution
This is the exact algorithm the Car Fleet visualizer steps through:
function carFleet(target, position, speed) {
// 1. Pair each position with its speed.
const cars = position.map((pos, i) => ({ pos, spd: speed[i] }));
// 2. Sort so the car closest to the target comes first.
cars.sort((a, b) => b.pos - a.pos);
const stack = []; // arrival time of each distinct fleet's leader
for (let car of cars) {
const timeToTarget = (target - car.pos) / car.spd;
stack.push(timeToTarget);
if (stack.length >= 2) {
const currentCarTime = stack[stack.length - 1];
const carAheadTime = stack[stack.length - 2];
// Reaches the target sooner-or-equal → blocked → merge.
if (currentCarTime <= carAheadTime) {
stack.pop();
}
}
}
// Whatever leaders remain are the distinct fleets.
return stack.length;
}The push-then-maybe-pop shape keeps the logic in one place: every car tentatively becomes a fleet, and only merges away if it's blocked. Note the comparison is against stack[length - 2] — the leader ahead — not against every earlier car. After a merge, the surviving leader's (larger) time stays on the stack, so the next car is correctly compared against the slowest fleet in front of it.
Walkthrough
Trace target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3].
After sorting descending by position, the order is car 0 (pos 10), car 1 (pos 8), car 3 (pos 5), car 4 (pos 3), car 2 (pos 0). Each arrival time is (12 - pos) / speed.
| Step | Car (pos, spd) | time = (12−pos)/spd | Stack after push | vs. ahead | Action |
|---|---|---|---|---|---|
| 1 | c0 (10, 2) | (12−10)/2 = 1.0 | [1.0] | — | first car, new fleet |
| 2 | c1 (8, 4) | (12−8)/4 = 1.0 | [1.0, 1.0] | 1.0 ≤ 1.0 | catches c0 → pop → [1.0] |
| 3 | c3 (5, 1) | (12−5)/1 = 7.0 | [1.0, 7.0] | 7.0 > 1.0 | too slow to catch → new fleet |
| 4 | c4 (3, 3) | (12−3)/3 = 3.0 | [1.0, 7.0, 3.0] | 3.0 ≤ 7.0 | catches c3's fleet → pop → [1.0, 7.0] |
| 5 | c2 (0, 1) | (12−0)/1 = 12.0 | [1.0, 7.0, 12.0] | 12.0 > 7.0 | slowest of all → new fleet |
Final stack [1.0, 7.0, 12.0] — size 3, so 3 fleets reach the target.
Step 2 is the tie case: cars 0 and 1 arrive at the exact same time, and the <= comparison correctly merges them (they finish together, so they're one fleet). Step 4 is the classic collision — car 4 could arrive in 3 seconds, but car 3 ahead of it needs 7, so car 4 slams into that fleet and inherits its pace.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(n) | each car rescans all others for a blocker |
| Sort + monotonic stack | O(n log n) | O(n) | sort dominates; the scan is one O(n) pass |
The sort is the bottleneck at O(n log n); the stack pass touches each car once and each car is pushed and popped at most once, so the merge logic is O(n) total. Space is O(n) for the paired-cars array and the stack.
Common mistakes
- Sorting ascending by position. Processing back-to-front means a car compares against cars behind it, which never block it. Sort descending so the top of the stack is always the fleet directly ahead.
- Using
<instead of<=. Two cars that arrive at the identical time are one fleet, not two. Dropping the equality (as in step 2 above) miscounts every tie. - Comparing against the wrong element. The blocker is the leader ahead —
stack[length - 2]right after the push. Comparing against the bottom of the stack or against the raw previous car in the input order gives wrong merges. - Simulating the road over time. Stepping positions forward frame by frame is slow, needs an arbitrary stop condition, and drowns in floating-point collision times. Collapse each car to a single arrival time instead.
- Dividing integers in a language without float division.
(target - pos) / speedmust be real division. In Python 3 use/, not//; in Java cast todouble.
Where this pattern shows up next
The monotonic stack — process elements in a deliberate order, keep a stack where each new item pops everything it "dominates" — is the shared engine behind a whole class of problems.
- Largest Rectangle in Histogram — the canonical monotonic-stack problem, where each bar pops taller bars it can no longer extend past. Same push-and-pop discipline, applied to areas instead of arrival times.
You can also step through Car Fleet interactively to watch the cars sort, the arrival times land on the stack, and each collision pop off in real time.
FAQ
Why do you sort cars by position instead of by speed?
Because collisions only happen between neighbors on the road, and position is what fixes that order. A car can only ever be blocked by the car directly ahead of it. Sorting descending by position guarantees that when you process a car, everything already on the stack is in front of it, so the top of the stack is exactly the fleet it might catch. Speed matters for when a car arrives, but position decides who it can run into.
Why does the current car merge when its time is less than or equal to the car ahead?
Arrival time is the free-driving time each car would take if the road were empty. If a car behind would reach the target sooner than (or exactly when) the car ahead, it must have closed the gap somewhere along the way — physically it catches up and gets stuck, since passing isn't allowed. From that point they move together at the slower leader's speed and arrive as one fleet. Equal times count as a merge too, because finishing simultaneously still means one clump crosses the line.
What is the time complexity of the Car Fleet solution?
O(n log n) time and O(n) space. The sort by position is the dominant cost at O(n log n). The stack pass that follows is O(n): each car is pushed once and popped at most once, so the merge checks add up to linear work. The extra space is the array of paired positions and speeds plus the stack of fleet arrival times, both at most n entries.
How does the stack size equal the number of fleets?
Every value left on the stack is the arrival time of a fleet leader — a car that never caught anyone ahead of it. When a trailing car merges, its time is popped off, so it stops counting as its own fleet. After processing every car, the only survivors are the leaders, one per distinct clump that reaches the target. Reading the stack's length is the same as counting those leaders.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.