Car Fleet — The Highway Convoy

Welcome back

Boss 5 introduced the monotonic stack. That was "find the next greater element." This boss is a different flavor: sorting + arrival time math + stack counting.

It's the kind of problem where the answer becomes obvious once you see the right framing, and confusing until then. Let's frame it right.

Today's boss: The Highway Convoy.

The story

A single-lane highway. Destination is at mile 12. No passing. If a fast car catches a slow car, it slows down and they travel as a fleet.

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

Car at position 10 going speed 2 reaches the target in (12-10)/2 = 1 hour. Car at position 8 going speed 4 takes (12-8)/4 = 1 hour. It arrives at the same time, so it's in the same fleet. Car at position 0 going speed 1 takes 12/1 = 12 hours. Car at position 5 going speed 1 takes (12-5)/1 = 7 hours. Car at position 3 going speed 3 takes (12-3)/3 = 3 hours. But it'll catch the car at position 5 (which takes 7 hours). So it merges into that fleet and takes 7 hours.

How many fleets arrive? 3.

The problem, dressed up properly

There are n cars going to the same destination along a one-lane road. You are given two integer arrays position and speed, each of length n, where position[i] is the position of the ith car and speed[i] is the speed.

A car can never pass another car ahead of it, but it can catch up and then drive at the same speed. A car fleet is some non-empty set of cars driving at the same position and same speed.

Return the number of car fleets that will arrive at the destination.

The key insight

Forget about simulating the cars moving. Think about arrival times.

For each car, compute: if this car had an empty road ahead, how long would it take to reach the target?

time[i] = (target - position[i]) / speed[i]

Now sort the cars by position, closest to the target first (descending position order).

Walk through the sorted cars. The car closest to the target sets the pace. If the next car behind it would arrive sooner (its time is smaller or equal), it catches up and merges — same fleet. If the next car behind would arrive later (its time is larger), it can never catch up — new fleet.

Watching it work

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

Pair them and sort by position descending:

(pos=10, spd=2, time=1.0)
(pos=8,  spd=4, time=1.0)
(pos=5,  spd=1, time=7.0)
(pos=3,  spd=3, time=3.0)
(pos=0,  spd=1, time=12.0)

Walk through:

Car pos=10, time=1.0 → stack empty, new fleet. Push 1.0.   stack: [1.0]
Car pos=8,  time=1.0 → `1.0 <= stack top 1.0` → merges.     stack: [1.0]
Car pos=5,  time=7.0 → 7.0 > stack top 1.0 → new fleet.   stack: [1.0, 7.0]
Car pos=3,  time=3.0 → `3.0 <= stack top 7.0` → merges.     stack: [1.0, 7.0]
Car pos=0,  time=12.0 → 12.0 > stack top 7.0 → new fleet. stack: [1.0, 7.0, 12.0]

Answer = len(stack) = 3 ✓

The code

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    # pair and sort by position descending (closest to target first)
    cars = sorted(zip(position, speed), key=lambda x: -x[0])
 
    stack = []  # arrival times of fleet leaders
 
    for pos, spd in cars:
        time = (target - pos) / spd
 
        if not stack or time > stack[-1]:
            # this car is slower than the fleet ahead — new fleet
            stack.append(time)
        # else: this car catches the fleet ahead — merges, do nothing
 
    return len(stack)

The stack here is simple — it just collects the arrival times of each fleet. You don't pop anything. You either push (new fleet) or skip (merge). The answer is the stack's length.

Technically you could just use a counter instead of a stack, but the stack makes the logic clearer and matches the pattern.

Why does this work?

The crucial insight is that no passing means position order is preserved forever. A car behind a slower car can never get ahead of it. So the arrival time of a car behind is effectively max(its own time, the time of the fleet ahead of it).

By processing closest-to-target first, when we encounter a car with a shorter arrival time than the fleet ahead, we know it will catch up and merge. When we encounter a car with a longer arrival time, it becomes a new fleet leader.

Complexity

• Sort: O(n log n)
• Stack walk: O(n)
• Total: O(n log n) time, O(n) space

Gotchas

1. Sorting in the wrong direction. Sort by position descending (closest to target first). If you sort ascending, the logic flips and becomes harder to reason about.

2. Using >= instead of >. If a car behind arrives at the exact same time as the fleet ahead, they merge. The check is time > stack[-1] for a new fleet, not >=. Equal times mean they arrive together — same fleet.

3. Integer division. (target - pos) / spd should be float division, not integer. In Python 3, / is float division by default. In other languages, cast to float first.

4. Thinking you need to simulate movement. You don't. The arrival time computation replaces simulation entirely. No time steps, no position updates. Pure math.

Boss down. XP gained.

You cleared Boss 6. The fleets are counted.

What you walked away with:

• The "compute arrival times, sort, stack-count" pattern
• The insight that sorting by position and comparing arrival times replaces simulation
• A clean O(n log n) solution for a problem that looks like it needs simulation

Next up: Boss 7 — The Billboard Builder. The final boss of Dungeon 3. Given a histogram (a row of bars of different heights), find the largest rectangle that fits inside it. This is the hardest monotonic stack problem and one of the most famous interview questions in existence.

Sharpen your pencil. This one's a fight.