← Create New Paste

Car Fleet (LeetCode 853): Sort by Position, Then Think in Arrival Times

3 views
Car Fleet is a medium problem that looks like a physics simulation but collapses into a few lines once you change how you look at it. There are n cars on a one-lane road heading to a target. Each car has a starting position and a speed. A faster car cannot pass a slower one; when it catches up, they move together as a fleet at the slower speed. Count how many fleets arrive at the target. Why simulation is the wrong path You could step time forward and merge cars, but time is continuous and speeds are arbitrary, so the simulation is messy and slow. Interviewers want to see you avoid it. Key insight 1: process cars from closest to the target A car can only be blocked by cars ahead of it. So sort cars by position in descending order and walk from the front of the road backward. Key insight 2: compare arrival times, not positions For each car, compute the time it would need to reach the target alone: (target - position) / speed. Now walk from front to back: - If a car's arrival time is greater than the current fleet's arrival time ahead of it, it can never catch up, so it starts a new fleet. - If its time is less than or equal, it catches the fleet ahead before (or exactly at) the target, so it merges and takes on that fleet's arrival time. Python def car_fleet(target, position, speed): cars = sorted(zip(position, speed), reverse=True) fleets = 0 slowest = 0.0 for pos, spd in cars: t = (target - pos) / spd if t > slowest: fleets += 1 slowest = t return fleets Time is O(n log n) for sorting, space O(n) for the pairs. The stack version Many solutions push arrival times onto a stack and pop when a car merges. That is the same idea; the single variable above is enough because only the most recent fleet's time matters. It is still worth mentioning, since interviewers who expect the stack pattern will recognize it. Edge cases to raise - Cars that meet exactly at the target count as one fleet, which is why the merge condition uses less than or equal. - A single car is one fleet. - Floating point: times are fractions. Comparing with floats is usually fine here, but you can compare cross-multiplied integers ((target - p1) * s2 versus (target - p2) * s1) if you want to be exact. Saying this shows care. How to explain it in an interview Start by stating that order matters only from the front, then introduce arrival time as the single number that summarizes each car. Walk through the sample: target 12, positions [10, 8, 0, 5, 3], speeds [2, 4, 1, 1, 3]. Times sorted by position are 1, 1, 7, 3, 12, giving fleets at 1, 7, and 12, so the answer is 3. Related problems The same "sort, then sweep with a running summary" idea appears in Car Fleet II, meeting room scheduling, and many greedy interval problems. Support during the interview If you tend to freeze when a problem looks like a simulation, Linkjob AI (https://linkjob.ai) provides real-time help during live job interviews and technical interviews, offering hints and structure while you reason it out in your own words.
Created Nov 17, 2026 16:34 Expires Nov 17, 2027 16:34