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 Plain-English Breakdown

Imagine a single-lane road where overtaking is physically impossible. Several cars are scattered along this road, all driving towards a single destination (the target). Since they can't overtake, if a fast car catches up to a slow car, it is forced to hit the brakes and match the slow car's speed. Together, they now form a "fleet". (A single car driving alone is also considered a fleet of 1). The question asks: by the time everyone reaches the target, how many distinct fleets will there be?

Constraints to note:

• n (number of cars) is up to 10^5, meaning an O(N \log N) sorting step is acceptable, but O(N^2) is not.
• Positions are unique.

Brute Force Analysis

A brute force simulation would involve advancing every car's position by its speed for a tiny time step dt, checking for collisions, merging cars that occupy the same space or pass each other, and repeating this until all cars cross the target.

• Why it fails: Simulating physics step-by-step is computationally massive. If the target is 10^6 miles away and speeds are 1 mph, you'd need a million simulation steps, doing O(N) work each step. It is entirely dependent on the scale of the input numbers, not just the array size. We need an analytical approach, not a simulation.

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.

ELI5 Analogy: Imagine standing at the finish line with a stopwatch. You look at the car closest to you and calculate: "If this car drives alone, it will arrive in 5 minutes." You write down 5. Then you look at the car behind it. You calculate its solo time: "If this car drives alone, it will arrive in 3 minutes." Wait! If the car behind takes 3 minutes but the car in front takes 5 minutes, they will crash! Since they can't overtake, the car behind gets stuck behind the first one. So you cross out the 3. You only write down a new time if the car behind takes longer than the one in front, meaning it never catches up.

Code Walkthrough

1. Zipping and Sorting: We pair up each car's starting position with its speed using zip(position, speed). We then sort this array in descending order (reverse=True). This puts the car closest to the target at index 0.
2. The Stack: We initialize an empty list fleets to act as our monotonic stack. It will store the arrival times of the fleets.
3. Calculating Time: As we loop through the sorted cars, we calculate the time it would take to reach the target if the car were driving alone: (target - pos) / spd.
4. The Stack Logic: We check if the stack is empty (this is the first car, closest to the finish line) OR if the current car's time is strictly greater than the time of the fleet at the top of the stack (fleets[-1]).
5. Forming a New Fleet: If the condition is met, this car is too slow to catch the fleet ahead of it. It becomes the leader of its own new fleet. We append its time to the stack.
6. Getting Absorbed: If the condition is NOT met (time \le fleets[-1]), the car is fast enough to catch the fleet ahead. It gets absorbed, so we do nothing. It doesn't change the arrival time of the fleet it joined.
7. Result: The length of the fleets stack is the number of fleets.

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.

Derivation:

• Time Complexity: Sorting an array of length N takes O(N \log N) time. The for loop simply iterates over the sorted array exactly once, performing O(1) arithmetic and stack operations per element, adding O(N) time. O(N \log N) + O(N) = O(N \log N).
• Space Complexity: O(N). We create a new array of tuples/arrays to hold the paired position and speed, which takes O(N) memory. The fleets stack can also grow up to N elements in the worst case where every car forms its own fleet (e.g., if every car is slower than the one ahead of it).

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.