Car Fleet

First, figure out how long each car would take to reach target if nothing were in its way: time = (target - position) / speed. A car cannot actually arrive later than a slower car in front of it — it just bunches up behind it instead, adopting that fleet’s arrival time.

So sort cars by starting position, front-most (closest to target) first, and walk through them. For each car, check every fleet already formed so far: if any of them arrives at the same time or later, this car catches up and joins it; otherwise it is its own new fleet.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        times = [(target - pos) / spd for pos, spd in cars]

        fleet_times = []
        for t in times:
            merged = False
            for ft in fleet_times:
                if ft >= t:
                    merged = True
                    break
            if not merged:
                fleet_times.append(t)
        return len(fleet_times)

This works, but re-scanning every previously formed fleet for each new car is wasteful — sorting is O(n log n), but the scan-and-check is O(n) per car in the worst case, giving O(n²) overall.

The brute force never actually needed to check every previous fleet — only the most recently formed one. Here’s why: once cars are sorted front-to-back, the sequence of fleet arrival times, in the order fleets are formed, is always non-decreasing. A car merges into the fleet directly ahead of it if it would otherwise arrive at the same time or sooner; if it is slower than the fleet ahead, it becomes a new, slower-arriving fleet. Either way, comparing against just the last fleet formed (the top of a stack) is enough — that stack is always sorted in increasing arrival time.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        stack = []  # arrival times of fleets formed so far, strictly increasing
        for pos, spd in cars:
            time = (target - pos) / spd
            if not stack or time > stack[-1]:
                stack.append(time)
            # else: this car catches up to and merges into the fleet on top
        return len(stack)

Tracing target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]. Sorted front-to-back by position: (10,2), (8,4), (5,1), (3,3), (0,1), giving unobstructed times [1.0, 1.0, 7.0, 3.0, 12.0]:

Correctness: because cars are processed front-to-back, a car can only ever be blocked by the fleet immediately ahead of it — a fleet further ahead is either already caught by that intermediate fleet or irrelevant, since cars cannot pass. This is exactly the invariant that lets a stack (only ever comparing against the top) replace scanning the whole history. Complexity: sorting is O(n log n); the single pass afterward does O(1) work per car since each car is pushed at most once and never revisited → O(n log n) total, O(n) space for the sort and stack.