Car Fleet

Car Fleet looks like a physics word problem, but it hides a clean pattern: sort, then sweep with a stack of arrival times. The trick is realizing you never need to simulate the cars moving — you only need to know when each one would reach the target.

The slow way first

You could simulate every car tick by tick, merging cars whenever a faster one bumps into a slower one ahead. That is fiddly and slow. The question to ask: what actually decides whether two cars end up in the same fleet? Only their arrival times at the target. If a car behind would arrive at the same time or sooner than the car ahead, it gets stuck behind it — same fleet.

The idea: sort, then stack arrival times

Compute each car arrival time time = (target - position) / speed. Then look at the cars from the one nearest the target backward. Keep a stack of fleet arrival times. For each car, compare its time to the stack top (the fleet directly ahead):

If a car arrival time is strictly greater than the stack top, it is slower than the fleet ahead and can never catch it — it leads a new fleet, so push its time. Otherwise it catches the fleet ahead and merges, so we leave the stack alone. The final stack size is the fleet count.

Walk through it

Step through the animation. Cars are already sorted by start position descending, and each cell shows its arrival time. The car pointer scans front to back. The first car (t=1) starts fleet 1. The next (t=1) is not slower, so it merges. The car with t=7 is slower, so it starts fleet 2; the t=3 car catches it and merges. The last car (t=12) trails alone, making fleet 3. Stack ends as [1, 7, 12] → 3.

Pseudocode

pair up each car as (position, speed)
sort cars by position, nearest the target first
stack = empty   # holds one arrival time per fleet
for each car in that order:
    time = (target - position) / speed
    if stack is empty OR time > top of stack:
        push time   # slower than the fleet ahead -> new fleet
    # else: it catches the fleet ahead and merges (do nothing)
return size of stack

The Python solution

def car_fleet(target, position, speed):
    order = sorted(range(len(position)),
                   key=lambda i: -position[i])
    stack = []
    for i in order:
        time = (target - position[i]) / speed[i]
        if not stack or time > stack[-1]:
            stack.append(time)
    return len(stack)

• order is the car indices sorted by position descending, so we process the car nearest the target first.
• stack holds one arrival time per fleet — its top is always the fleet directly ahead of the current car.
• time = (target - position[i]) / speed[i] is how long this car would take to reach the target on its own.
• Lines 7–8 are the decision: a car only starts a new fleet when its time is strictly greater than the stack top (it is too slow to catch up). Otherwise it merges and the stack is untouched.
• len(stack) is the number of distinct fleets that reach the target.

Complexity

Sorting dominates at O(n log n); the sweep is linear and the stack uses O(n) extra space. You never simulate motion — arrival times plus one stack pass are enough.

When this pattern shows up

Practice