LeetCode 853 · Stack

Car Fleet, explained with a picture

Cars bunching into convoys on a one-lane road.

MediumStack
▶ Watch it step by step

The problem

Cars drive toward a finish line on a single-lane road. Each car has a starting position and speed. A car cannot pass the one in front; if it catches up, they move together as a fleet at the slower speed. How many fleets reach the finish?

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

Picture it

Picture the cars on the road and work from the car nearest the finish backwards. For each car compute arrival time = remaining distance ÷ speed. If a car behind would arrive sooner than (or at the same time as) the fleet in front of it, it catches up and joins that fleet. If it would arrive later, it can never catch up, so it starts a new fleet.

How to recognise it

  • Things move along one line and cannot overtake, so what happens to an item depends only on the items ahead of it.
  • Each item has a single number that decides its fate: here the time it would take to reach the target alone, (target - pos) / spd.
  • Processing items in order of position (front to back) turns "who blocks whom" into a comparison with the group just ahead. That is a sort plus a stack (or a running maximum).
  • Up to 10^5 cars, so comparing every car with every car ahead of it is too slow.

Start with brute force

Compute each car's solo arrival time. A car leads its own fleet exactly when it would arrive later than every car in front of it; otherwise it catches some car ahead and joins that car's fleet. Count the leaders.

def car_fleet_brute(target, position, speed):
    n = len(position)
    times = [(target - position[i]) / speed[i] for i in range(n)]
    fleets = 0
    for i in range(n):
        # car i leads a fleet if it is slower to arrive than every car ahead
        if all(times[i] > times[j] for j in range(n) if position[j] > position[i]):
            fleets += 1
    return fleets

Time is O(n²) because each car looks at every other car, and space is O(n) for the times. For n = 10^5 that is about 10^10 comparisons.

From brute force to the idea

  1. Find the waste. Each car only needs the largest arrival time among the cars in front of it, but the brute force recomputes that maximum from scratch for every car.
  2. Sort front first. sorted(zip(position, speed), reverse=True) lists the car nearest the target first. Now "the cars in front" are exactly the cars already processed.
  3. A fleet arrives when its slowest leader does. Cars that catch up slow down, so a fleet reaches the target at its leading car's solo time.
  4. Compare with the fleet just ahead. If a car's time t is greater than fleets[-1], it can never catch that fleet, so it starts a new one and its time is pushed. Otherwise it catches up at or before the target and merges, so nothing is pushed.
  5. The answer is the number of fleets. Each pushed time is one fleet, so return len(fleets).

The times in fleets only ever increase, so the list never pops: fleets[-1] is simply the running maximum. A counter plus one variable would work just as well.

This is the key idea: sort by position from the front, then a car starts a new fleet only if it is slower than the slowest fleet ahead.

The key idea

Sort by position (closest to the finish first) and compare arrival times; a new fleet starts only when a car is slower to arrive than the fleet ahead.

Python solution

def car_fleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)  # front first
    fleets = []                    # arrival time of each fleet
    for pos, spd in cars:
        t = (target - pos) / spd
        if not fleets or t > fleets[-1]:
            fleets.append(t)       # too slow to catch up: new fleet
        # else: catches the fleet ahead and joins it
    return len(fleets)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every car checks every car aheadO(n): the arrival times
Sort + fleet list (shown code)O(n log n): the sort dominates; the loop is O(n)O(n): the sorted pairs and the fleet times

Edge cases

  • One car: returns 1.
  • Catching up exactly at the target (target 10, positions [0, 5], speeds [2, 1]): both take 5 hours, t > fleets[-1] is false, so they count as one fleet, as LeetCode requires.
  • Everyone catches the front car (target 100, positions [0, 2, 4], speeds [4, 2, 1]): returns 1.
  • The example returns 3, with fleets of 2, 2 and 1 cars.
  • Floating-point times: with targets and speeds up to 10^6, two different exact times differ by far more than the rounding error of a division, so floats are safe here. Comparing (target - p1) * s2 with (target - p2) * s1 avoids floats entirely.

Common mistakes

  • Sorting by speed or by time instead of by position. Blocking depends on who is in front.
  • Sorting from the back (ascending position). The comparison then checks a car against the cars behind it, so two equal-speed cars, which never meet, are wrongly merged.
  • Using >= to start a new fleet, which splits cars that arrive at the same moment.
  • Simulating the cars hour by hour. Times are fractions, so a step-by-step simulation is both slow and inexact.
Your turn: how big is each fleet?

Return the number of cars in each fleet, listed from the fleet that arrives first to the last. For the example the answer is [2, 2, 1]. Describe your approach, then write it if you like.

Compare with our answer

Process cars front first exactly as before. When a car starts a new fleet, append a size of 1; when it merges, add 1 to the last size.

def fleet_sizes(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    times, sizes = [], []
    for pos, spd in cars:
        t = (target - pos) / spd
        if not times or t > times[-1]:
            times.append(t)
            sizes.append(1)
        else:
            sizes[-1] += 1          # joins the fleet just ahead
    return sizes

The sizes add up to n, and len(sizes) equals the shown code's answer. Time O(n log n), space O(n).

A strong answer mentions: that a merging car always joins the most recent fleet (not an earlier one), why the front fleet arrives first, and checking that the sizes sum to the number of cars.

Check what stuck

1. Runners on a narrow track cannot pass; a faster runner who catches up must jog behind. You must count the groups that cross the line. Which approach fits best?

2. Why is the shown code O(n log n) rather than O(n)?

3. A learner sorts with sorted(zip(position, speed)), back car first, and keeps the rest unchanged. Which input now gives a wrong count?

Score 60% or more and the lesson is marked complete.