4.8.6 — Car Fleet

LeetCode 853 · Medium

The problem

Cars are driving towards a target at position target. Car i starts at position[i] and drives at speed[i]. Cars cannot overtake. When a faster car catches a slower one, it slows down and they travel together as a fleet from then on.

How many fleets arrive at the target?

target = 12
position = [10, 8, 0, 5, 3]
speed    = [ 2, 4, 1, 1, 3]
→ 3

The pattern

The physics wording hides a simple question. Reduce it in two steps.

Step 1 — every car has an arrival time if nothing blocks it.

t_i = \frac{\text{target} - \text{position}_i}{\text{speed}_i}

Step 2 — sort the cars by position, closest to the target first. Then walk from the front of the road backwards.

Now the rule: a car catches the fleet ahead of it exactly when it would arrive sooner than that fleet does. If it would arrive later, it can never catch up, so it starts a fleet of its own.

So walk from the front and keep the arrival times of the fleets you have created. A car whose time is greater than the last fleet's time becomes a new fleet. A car whose time is less than or equal gets absorbed, and it does not change the fleet's arrival time, because the fleet still travels at the speed of its slowest, front-most car.

That is a monotonic stack: the times on it are strictly increasing from the front of the road backwards, and anything that would be smaller gets swallowed.

The solution

Python

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)   # closest to target first
        fleets = []

        for pos, spd in cars:
            time = (target - pos) / spd                     # float division
            if not fleets or time > fleets[-1]:
                fleets.append(time)                         # a new, slower fleet

        return len(fleets)

TypeScript

function carFleet(target: number, position: number[], speed: number[]): number {
  const cars = position
    .map((p, i) => [p, speed[i]] as [number, number])
    .sort((a, b) => b[0] - a[0]);            // closest to target first

  const fleets: number[] = [];

  for (const [pos, spd] of cars) {
    const time = (target - pos) / spd;
    if (fleets.length === 0 || time > fleets[fleets.length - 1]) {
      fleets.push(time);
    }
  }

  return fleets.length;
}

Sort descending by position. Processing the car nearest the target first is what makes "the fleet ahead" always be the last thing you looked at.

> and not >=. Two cars arriving at exactly the same moment are one fleet, since they meet at the target.

You only ever compare against the last fleet, not all of them. If a car cannot catch the fleet directly ahead, it certainly cannot catch anything further ahead, because those arrive even earlier. So one comparison is enough.

You never actually need the stack. Since only the last element is ever read, a single variable holding the last fleet's time and a counter would do. The list is kept here because it makes the monotonic structure visible, and because an interviewer often wants to see it. Say that you noticed.

Trace

target = 12, cars sorted by position descending:

position	speed	time to target	fleet?
10	2	(12−10)/2 = 1.0	new fleet (1.0)
8	4	(12−8)/4 = 1.0	1.0 is not > 1.0 → absorbed
5	1	(12−5)/1 = 7.0	7.0 > 1.0 → new fleet
3	3	(12−3)/3 = 3.0	3.0 is not > 7.0 → absorbed
0	1	(12−0)/1 = 12.0	12.0 > 7.0 → new fleet

Three fleets.

The car at position 3 is the interesting one. On its own it would arrive at time 3, sooner than the fleet ahead which arrives at 7. So it catches that fleet and joins it. It never becomes its own fleet even though it is fast.

The division trap

Use float division, not integer division.

The car at position 10 with speed 4 would take 0.5 units of time. With integer division that becomes 0, and it looks identical to a car already at the target. The comparisons then go wrong and the fleet count is too low.

In Python that means /, never //. In JavaScript / is already float, so nothing to do. This is the same floor-versus-truncate family of bug as 4.8.3, and your Report 2 flagged both.

If you wanted to avoid floating point entirely — which is what you would do in production, where accumulated rounding can flip a comparison — compare the fractions by cross-multiplying:

\frac{a}{b} > \frac{c}{d} \iff a \cdot d > c \cdot b \quad\text{(for positive } b, d)

Mentioning this unprompted is a strong signal, because it shows you know that a comparison of two divisions never needs the divisions.

Complexity

O(n \log n), dominated by the sort. The scan afterwards is O(n). Space is O(n) for the sorted pairs.

Note that the sort is not optional here, and it is not a convenience: the problem is meaningless without knowing which car is in front of which.

Language note

Python's sorted(zip(position, speed), reverse=True) builds tuples and sorts them by first element, then second. It is concise and runs in C.

JavaScript needs the explicit comparator (a, b) => b[0] - a[0], because the default sort() compares as strings — [10, 9] would sort as [10, 9]. Forgetting the comparator is one of the most common JavaScript bugs in coding problems.

Where this goes next

• Asteroid Collision (LeetCode 735) — asteroids moving in opposite directions destroy each other. A stack, where the collision is the eviction event.
• Remove K Digits — evict a larger digit when a smaller one arrives, to build the smallest result.
• Any "who blocks whom" question — traffic, scheduling with dependencies, task pipelines where a slow stage caps the ones behind it.

The rule: when one item permanently constrains everything behind it, sort into that order and keep only the constraints that still matter.

What the interviewer will push on

"Why sort by position?" Because the fleet ahead is what matters, and only the ordering along the road tells you which car that is.

"Why compare only with the last fleet?" Anything further ahead arrives even sooner, so failing to catch the nearest fleet means failing to catch any.

"Why float division?" Integer division truncates fractional arrival times to 0 and corrupts the comparisons. Then offer the cross-multiplication alternative.

"Do you actually need a stack?" No — one variable suffices. Say so; it shows you understood the algorithm rather than pattern-matched to the chapter title.

"What if cars could overtake?" Then there are no fleets at all and the answer is just the number of cars. The no-overtaking rule is what creates the whole problem.

One thing to volunteer: state the reduction in one sentence before coding. "Sort by position from the target backwards, compute each car's solo arrival time, and count how many times the time increases."

Next: 4.8.7 Largest Rectangle in Histogram — the hardest monotonic stack problem, and the one where "compute on eviction" finally pays for itself.