Car Fleet LeetCode 853 — Stack Guide

LeetCode 853 — Car Fleet — places n cars on a one-lane road heading toward a single target destination. Each car has a starting position and a speed. Because it is a one-lane road, a faster car that catches up to a slower car in front cannot pass — instead it slows down and the two cars form a fleet that travels together at the slower car's speed. A single car that reaches the target alone also counts as a fleet. Your task is to count how many fleets arrive at the target.

The problem guarantees no two cars start at the same position, and all cars start behind the target. Because overtaking is impossible, a car that catches a slower fleet merges into it permanently. Fleets are not split — once two cars merge, they travel as one unit for the rest of the journey. The count you return is the number of groups (fleets) that ultimately reach the target.

LeetCode 853 is rated Medium. The brute force approach simulates each car step by step, which is complex and slow. The elegant solution uses sorting by position and a monotonic stack on arrival times, achieving O(n log n) time for the sort and O(n) space for the stack.

The key insight is that overtaking is impossible. If car A is behind car B and car A would arrive at the target faster (shorter arrival time), car A will catch car B before the target and merge into car B's fleet. Car A cannot arrive earlier than car B — it is stuck behind car B for the rest of the journey. This means we only need to know whether car A's solo arrival time is less than or equal to car B's arrival time to determine if they form one fleet.

Sorting cars by position in descending order — closest to target first — allows us to process cars from front to back. Each car either forms a new fleet (its arrival time is greater than the car in front) or merges into the fleet ahead (its arrival time is less than or equal to the car in front). Processing front to back ensures we always know the arrival time of the fleet immediately ahead before we evaluate the current car.

The arrival time for each car is computed as (target - position) / speed. This is the time the car would take to reach the target if it drove alone, ignoring all other cars. It does not simulate actual travel — it is simply the solo arrival time used as a proxy for whether the car catches the fleet ahead.

For each car, the arrival time is (target - position) / speed. This gives the number of time units the car would take to reach the target if it drove the entire distance alone at its given speed, with no other cars on the road. It is a floating-point value — use true division, not integer division, to avoid incorrect comparisons.

The arrival time does not represent the actual time the car reaches the target in the simulation with fleets. It is a solo-trip proxy: a car with a smaller arrival time than the car directly ahead will catch up to that fleet before the target. A car with a larger arrival time will not catch up and forms its own fleet. This proxy is sufficient because once a car merges, it inherits the fleet's speed and arrival time — the fleet's arrival time equals the slowest car's solo arrival time.

After pairing each position with its speed and sorting by position descending, compute the arrival time array in a single pass. You can compute arrival times inline during the stack traversal rather than materializing a separate array — both approaches are equally correct.

Iterate through the sorted cars and maintain a stack of arrival times representing distinct fleets. For each car, compute its arrival time. If the stack is empty or the current car's arrival time is greater than the top of the stack, the current car cannot catch the fleet ahead — push its arrival time as a new fleet. If the current car's arrival time is less than or equal to the stack top, the car merges into the fleet ahead — do not push.

The stack height at the end of the iteration equals the number of distinct fleets that reach the target. Each entry in the stack represents one fleet that could not be absorbed by the fleet directly ahead of it. The stack grows by one for each new fleet and stays the same size for each merge. You never pop from the stack — elements are only pushed or skipped.

This is a monotonic non-decreasing stack on arrival times from bottom to top: each new fleet that gets pushed has an arrival time strictly greater than the fleet ahead (stack top). If you push an arrival time equal to the stack top, the cars arrive simultaneously — still one fleet. Only arrival times strictly greater than the top are pushed.

Trace target=12, position=[10,8,0,5,3], speed=[2,4,1,1,3]. First, pair and sort by position descending: [(10,2), (8,4), (5,1), (3,3), (0,1)]. Compute arrival times: car at 10 → (12-10)/2=1.0, car at 8 → (12-8)/4=1.0, car at 5 → (12-5)/1=7.0, car at 3 → (12-3)/3=3.0, car at 0 → (12-0)/1=12.0.

Now iterate with the stack. Car at 10: stack empty, push 1.0. Stack: [1.0]. Car at 8: arrival=1.0, stack top=1.0, 1.0 <= 1.0 so merge — do not push. Stack: [1.0]. Car at 5: arrival=7.0 > 1.0, new fleet — push 7.0. Stack: [1.0, 7.0]. Car at 3: arrival=3.0 <= 7.0, merge — do not push. Stack: [1.0, 7.0]. Car at 0: arrival=12.0 > 7.0, new fleet — push 12.0. Stack: [1.0, 7.0, 12.0].

Final stack has 3 entries, so the answer is 3 fleets. Fleet 1: cars at positions 10 and 8 (both arrive at time 1.0). Fleet 2: car at position 5 (arrives at 7.0) with car at position 3 merging in (would arrive at 3.0 alone but is blocked). Fleet 3: car at position 0 (arrives at 12.0 alone).

Python solution: def carFleet(target, position, speed): pairs = sorted(zip(position, speed), reverse=True); stack = []; for pos, spd in pairs: t = (target - pos) / spd; if not stack or t > stack[-1]: stack.append(t); return len(stack). Sort by position descending using reverse=True. For each car compute arrival time t. If the stack is empty or t is strictly greater than the top, push — new fleet. Otherwise skip — the car merges. Return the stack length. Time O(n log n) for sort, O(n) space for stack.

Java solution: public int carFleet(int target, int[] position, int[] speed) { int n = position.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> position[b] - position[a]); Deque<Double> stack = new ArrayDeque<>(); for (int i : idx) { double t = (double)(target - position[i]) / speed[i]; if (stack.isEmpty() || t > stack.peek()) stack.push(t); } return stack.size(); }. Java sorts an index array by position descending. Each arrival time is computed as a double to avoid integer division. The Deque acts as a stack with push/peek. Return stack.size().

Both solutions share the same three-step structure: sort by position descending, compute arrival times, count fleets with a stack. The Python solution is more concise using zip and sorted with reverse=True. The Java solution uses an index sort since Java cannot easily sort parallel arrays. The key in both languages is using floating-point division for arrival times — integer division would incorrectly truncate times like (12-10)/2=1 vs (12-11)/1=1, making them appear equal when they should not be compared as integers.

Daily Temperatures (LeetCode 739) is the most direct relative — a monotonic decreasing stack of indices where each pop resolves a waiting day's answer. Unlike Car Fleet where you never pop, Daily Temperatures pops eagerly when a warmer day is found. Both problems share the core pattern: sort or scan in a natural order, use a stack to track unresolved elements, resolve them when a triggering condition is met.

Asteroid Collision (LeetCode 735) uses a stack where right-moving asteroids are pushed and left-moving asteroids trigger pops — similar to the merge logic in Car Fleet. Next Greater Element (LeetCode 496, 503) and Largest Rectangle in Histogram (LeetCode 84) round out the monotonic stack family. Histogram is the hardest variant, requiring pops with width computations on both sides.

The monotonic stack pattern appears in: next/previous greater or smaller element, span counting (Online Stock Span, LeetCode 901), fleet merging (Car Fleet), and area maximization (Histogram, Trapping Rain Water). Once you master the sorting-plus-stack approach in Car Fleet, the natural next step is Online Stock Span where the stack stores (price, span) pairs and spans accumulate on each pop.