n cars head to the same destination on a one-lane road, each with a starting position and speed. A car that catches up to a slower car ahead is stuck behind it, and together they travel as one "fleet" at the slower car's speed. Return the number of distinct fleets that will arrive at the destination.
Example
Input target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output 3
Key Pointers
Sort cars by starting position, closest to the target first — only a car's time-to-target matters for whether it catches the car ahead.
Each car's time to reach the target is (target - position) / speed.
Processing from closest-to-target backward: a car merges into the fleet ahead if its own time-to-target is less than or equal to that fleet's time; otherwise it forms a brand new fleet.
Step-by-Step Analysis
Pair each car's position with its speed, and sort the pairs by position in descending order (closest to target first).
Compute each car's time-to-target as (target - pos) / speed.
Walk the sorted cars, keeping a stack of fleet arrival times: if a car's time is less than or equal to the time on top of the stack, it merges into that fleet — don't push anything new.
If a car's time is greater than the top of the stack, it leads a new fleet — push its time.
The final stack size is the number of fleets.
Complexity
Time: O(n log n) for the sort — Space: O(n)
Code
def carFleet(target: int, position: list[int], speed: list[int]) -> int:
cars = sorted(zip(position, speed), reverse=True)
stack = []
for pos, spd in cars:
time = (target - pos) / spd
if not stack or time > stack[-1]:
stack.append(time)
return len(stack)
Code Explanation
How the solution above works, piece by piece.
sorted(zip(position, speed), reverse=True): process cars from the one nearest the target backwards. A car can only be blocked by cars in front of it.
time = (target - pos) / spd: when this car would arrive if nothing blocked it.
If it would arrive later than the fleet directly ahead (time > stack[-1]), it never catches up: push it as a new fleet.
Otherwise it catches that fleet before the target and moves at its speed from then on, so it adds nothing.
len(stack) is the number of fleets. Sorting dominates: O(n log n).
Visual Walkthrough
Running it on target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]:
Cars (circles, labelled with speed) are handled from the one closest to the target backwards. A car that would arrive no later than the fleet in front catches it and merges; a slower car starts a new fleet. Colours show the 3 fleets.