1. Arrival time
Time to reach the target is distance over speed.
(target - pos) / speed[i]Typorithm · medium
Car Fleet
car-fleetmonotonic-stacksort-by-positionarrival-timefleet-merge
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Car Fleet
Monotonic Stack
Sort cars from closest to target; a car arriving later than the fleet ahead starts a new fleet, counted by the stack.
Each car's arrival time is the remaining distance divided by its speed.
Processing cars from closest to the target, a car that would arrive after the one ahead can never catch it, so it forms a new fleet.
A car that would arrive sooner is blocked and merges into the fleet ahead.
01
Arrival time = (target - pos) / speed.
02
Sort by position descending.
03
Later arrival than the lead = new fleet.
function carFleet(target, position, speed) {
const cars = position
.map((pos, i) => [pos, (target - pos) / speed[i]])
.sort((a, b) => b[0] - a[0]);
const stack = [];
for (const [, time] of cars) {
if (stack.length === 0 || time > stack[stack.length - 1]) {
stack.push(time);
}
}
return stack.length;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Closest first
Sort by position descending so the lead car comes first.
.sort((a, b) => b[0] - a[0])3. New fleet?
A slower (later-arriving) car starts a new fleet ahead.
if (stack.length === 0 || time > stack[stack.length - 1]) {4. Fleet count
The stack size is the number of distinct fleets.
return stack.lengthA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.