Car Fleet
Count the car fleets that reach a target by sorting cars from the front back and keeping a stack of fleet arrival times.
Problem Understanding
Car Fleet: cars drive toward target on a one-lane road. A car can't pass the one ahead; if it catches up, it slows down and they move together as a fleet. Given each car's starting position and speed, return how many fleets arrive at the target.
Example: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3] returns 3.
The Intuition: Arrival Times From the Front Back
The front car is never held up, so start there. For each car, work out when it would arrive on its own: (target − position) / speed.
Now walk backwards through the cars. Compare each car's time with the fleet just ahead of it:
- Later time: it can never catch up, so it leads a new fleet.
- Earlier or equal time: it catches the fleet ahead before the target and joins it.
Keep the fleets' arrival times on a stack. Because a new fleet is only pushed when it is slower, the times on the stack only increase, which makes this a monotonic stack. The number of entries is the answer.
Interactive Walkthrough
The table lists the cars from the front back, with each one's time on its own and the fleet it ends up in. The stack of fleet arrival times grows beside it whenever a car is too slow to catch the fleet ahead.
Dry Run Table
Input: target = 12, cars (position, speed) (10, 2), (8, 4), (0, 1), (5, 1), (3, 3)
| Car (sorted) | Time alone | vs top | Stack |
|---|---|---|---|
| 10, speed 2 | 1 | empty: push | [1] |
| 8, speed 4 | 1 | 1 ≤ 1: merge | [1] |
| 5, speed 1 | 7 | 7 > 1: push | [1, 7] |
| 3, speed 3 | 3 | 3 ≤ 7: merge | [1, 7] |
| 0, speed 1 | 12 | 12 > 7: push | [1, 7, 12] |
3 fleets.
The Solution Template
Sort by position descending, then keep only times that are slower than the fleet ahead. The C snippet keeps just the last fleet's time instead of a whole stack.
Car Fleet Code
1var carFleet = function(target, position, speed) {2 const cars = position.map((p, i) => [p, speed[i]]).sort((a, b) => b[0] - a[0]);3 const stack = [];4 for (const [p, s] of cars) {5 const t = (target - p) / s;6 if (!stack.length || t > stack[stack.length - 1]) stack.push(t);7 }8 return stack.length;9};
Edge Cases & Common Mistakes
- Equal arrival times: a car that arrives exactly when the fleet ahead does joins it; use
>, not>=, to push. - Integer division: compute the time as a floating-point number, or compare with cross-multiplication.
- Sorting by speed: the order must be by position, front to back.
- Comparing with every earlier car: only the fleet directly ahead (the top) matters.
Summary
Sort cars from closest to the target to farthest and compute each one's solo arrival time. A car slower than the fleet ahead starts a new fleet; a faster one merges. Keep fleet times on a stack (or just the last one) and return how many there are. O(n log n) for the sort.
More practice: DSA interview questions with answers · patterns cheat sheet