Car Fleet: how arrival time collapses a simulation into a stack sweep

The first instinct on Car Fleet is usually simulation. You have cars at different positions moving at different speeds toward a target, and you want to count how many groups arrive together. It feels like you should step through time, update positions, check for collisions. That approach works conceptually and collapses completely under the constraints: target goes up to 10^6, n goes up to 10^5, and a time-step simulation is O(target * n) — roughly 10^11 operations in the worst case.

The insight that unlocks the efficient solution is a substitution: instead of tracking where cars are at each moment, compute how long each car takes to reach target if left alone. Two cars form a fleet if and only if the trailing car would arrive no later than the leading car. The leading car acts as a ceiling — the trailing car either catches up at or before target, or it does not. You never need to know exactly where they meet.

That reduction turns a simulation into a single pass with a stack.

The problem

There are n cars traveling toward a mile target on a one-lane road. Each car has a starting position and a speed; a car cannot pass the car ahead of it but can catch up and travel alongside it at the slower car's speed. A car fleet is one car or a group of cars moving together — a car that catches a fleet at exactly target still counts as part of it. Return the number of fleets that reach target. Full statement: LeetCode 853.

Constraints:
- n == position.length == speed.length
- 1 <= n <= 10^5
- 0 < target <= 10^6
- 0 <= position[i] < target
- All the values of position are unique.
- 0 < speed[i] <= 10^6

What the constraints force

n == position.length == speed.length, 1 <= n <= 10^5, 0 < target <= 10^6. All positions are unique. All speeds are positive.

The unique-position guarantee matters more than it looks. It means no two cars start at the same mile, so you never have to handle a tie at the starting line. The sorted order after you zip and sort on position is always strict.

n <= 10^5 rules out O(n^2). Any solution that compares every pair of cars is out. The size invites O(n log n), which is exactly where the sort lands you.

The speed bound speed[i] <= 10^6 combined with target <= 10^6 means arrival times fit in a double without precision problems. The maximum arrival time is (10^6 - 0) / 1 = 10^6 hours — well within floating-point range.

Approach 1: brute-force simulation

The honest brute force is to step through time in discrete increments. At each tick, advance every car by its speed (clamped to target). If a car's position reaches or passes a car ahead of it, they merge and the merged group takes the minimum speed.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        # Pair up cars and sort by starting position ascending
        cars = sorted(zip(position, speed))
        n = len(cars)
 
        # groups[i] = (current_position, current_speed, fleet_id)
        # Merge when a trailing group catches the leading group
        groups = [[pos, spd, i] for i, (pos, spd) in enumerate(cars)]
 
        # Step through time in increments of 1 (integer time steps)
        # This is illustrative -- real target can be 10^6, making this O(target*n)
        arrived = [False] * n
        fleet_map = list(range(n))  # fleet_map[i] = canonical fleet leader index
 
        time = 0
        while not all(arrived):
            time += 1
            # Advance each group
            for g in groups:
                if not arrived[fleet_map[g[2]]]:
                    g[0] = min(g[0] + g[1], target)
 
            # Check merges: scan left to right (ascending position)
            for i in range(n - 1):
                if arrived[fleet_map[groups[i][2]]]:
                    continue
                for j in range(i + 1, n):
                    if groups[j][0] >= groups[i][0]:
                        # j caught i -- j joins i's fleet, takes i's speed
                        if fleet_map[groups[j][2]] != fleet_map[groups[i][2]]:
                            old = fleet_map[groups[j][2]]
                            new = fleet_map[groups[i][2]]
                            for k in range(n):
                                if fleet_map[groups[k][2]] == old:
                                    fleet_map[groups[k][2]] = new
                            groups[j][1] = groups[i][1]
                    else:
                        break
 
            for g in groups:
                if g[0] >= target:
                    arrived[fleet_map[g[2]]] = True
 
        return len(set(fleet_map))

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
        // Pair and sort ascending by position
        var cars = new (int pos, int spd)[n];
        for (int i = 0; i < n; i++) cars[i] = (position[i], speed[i]);
        Array.Sort(cars, (a, b) => a.pos.CompareTo(b.pos));
 
        double[] pos = new double[n];
        double[] spd = new double[n];
        for (int i = 0; i < n; i++) { pos[i] = cars[i].pos; spd[i] = cars[i].spd; }
        int[] fleet = new int[n];
        for (int i = 0; i < n; i++) fleet[i] = i;
 
        bool[] done = new bool[n];
        int time = 0;
        while (true) {
            time++;
            for (int i = 0; i < n; i++)
                if (!done[fleet[i]])
                    pos[i] = Math.Min(pos[i] + spd[i], target);
 
            for (int i = 0; i < n - 1; i++) {
                if (done[fleet[i]]) continue;
                for (int j = i + 1; j < n; j++) {
                    if (pos[j] >= pos[i] && fleet[j] != fleet[i]) {
                        int old = fleet[j], nw = fleet[i];
                        for (int k = 0; k < n; k++)
                            if (fleet[k] == old) { fleet[k] = nw; spd[k] = spd[i]; }
                    } else if (pos[j] < pos[i]) break;
                }
            }
 
            bool allDone = true;
            for (int i = 0; i < n; i++)
                if (pos[i] >= target) done[fleet[i]] = true;
                else allDone = false;
            if (allDone) break;
        }
 
        var seen = new System.Collections.Generic.HashSet<int>(fleet);
        return seen.Count;
    }
}

Time: O(target * n). At each time step you touch every car, and you may need up to target steps. With target = 10^6 and n = 10^5, that is 10^11 operations — completely infeasible.

Space: O(n) for the working arrays.

The brute force is instructive because it makes the fleet-merging rule concrete. But nobody ships this. It exists in the article because seeing why it fails drives home what the efficient solution is actually exploiting.

Approach 2: sort by position, stack arrival times

The key insight: a car at position p with speed s arrives at target in (target - p) / s hours if nothing blocks it. Whether it gets blocked depends entirely on whether the car immediately ahead of it (in the sorted order, i.e., the next car closer to target) arrives first. If the car ahead arrives earlier (smaller arrival time), it is already gone before the trailing car reaches its position — no fleet. If the car ahead arrives later (larger arrival time), the trailing car catches up and they form a fleet.

There is a crucial direction: you must process cars from closest-to-target to furthest. A car can only be blocked by a car between it and the target, not by a car behind it. Processing front-to-back means every car you consider has already resolved whether it leads a fleet or merges into one ahead.

The stack stores the arrival times of fleet leaders encountered so far. When you process a car:

• If its arrival time is greater than the top of the stack, it cannot catch the fleet ahead. It is a new fleet leader. Push it.
• If its arrival time is less than or equal to the top, it will catch up to the fleet ahead (at or before target). It is absorbed. Do nothing.

At the end, the stack height is the number of fleets.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        # Sort descending by position: process closest-to-target first
        cars = sorted(zip(position, speed), reverse=True)
 
        stack = []  # arrival times of fleet leaders
 
        for pos, spd in cars:
            arrival = (target - pos) / spd
 
            # This car is a new fleet leader if it cannot catch the fleet ahead
            if not stack or arrival > stack[-1]:
                stack.append(arrival)
            # Otherwise (arrival <= stack[-1]): absorbed into the leading fleet
 
        return len(stack)

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
 
        // Zip and sort descending by position
        var cars = new (int pos, int spd)[n];
        for (int i = 0; i < n; i++) cars[i] = (position[i], speed[i]);
        Array.Sort(cars, (a, b) => b.pos.CompareTo(a.pos));
 
        var stack = new Stack<double>();
 
        foreach (var (pos, spd) in cars) {
            double arrival = (double)(target - pos) / spd;
 
            if (stack.Count == 0 || arrival > stack.Peek()) {
                stack.Push(arrival);
            }
            // arrival <= stack.Peek(): this car merges into the fleet ahead
        }
 
        return stack.Count;
    }
}

Time: O(n log n) — dominated by the sort. The linear scan with the stack is O(n), each push/peek is O(1).

Space: O(n) for the sorted array and the stack. In the worst case (every car forms its own fleet), the stack holds n arrival times.

Hand trace: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Step 1 — compute arrival times for each car:

pos=10, spd=2 -> arrival = (12-10)/2 = 1.0
pos=8,  spd=4 -> arrival = (12-8)/4  = 1.0
pos=5,  spd=1 -> arrival = (12-5)/1  = 7.0
pos=3,  spd=3 -> arrival = (12-3)/3  = 3.0
pos=0,  spd=1 -> arrival = (12-0)/1  = 12.0

Step 2 — sort descending by position and process:

Car at pos=8 has the same arrival time as pos=10 — it catches up exactly at mile 12, which the problem explicitly says still counts as the same fleet. The <= in the comparison handles this.

Car at pos=3 arrives in 3 hours. The fleet ahead (rooted at pos=5) arrives in 7 hours. Three hours is less than seven, so pos=3 catches the pos=5 fleet before target. They merge.

Three stacks entries remain: the 1.0-hour fleet (pos=10+pos=8), the 7.0-hour fleet (pos=5+pos=3), and the solo 12.0-hour car at pos=0. Output: 3.

Edge cases that actually matter

Single car (n = 1): the loop runs once, the stack is empty on entry, the car is pushed. Stack length is 1. Correct.

All cars at same speed with different positions: since positions are unique and speeds are equal, (target - pos) / spd is strictly decreasing as position increases. Every car's arrival time is larger than the car ahead of it. Every car is a new fleet leader. Output equals n. The stack fills up entirely.

Fastest car is closest to target: example 3 from the problem. Car at pos=4, spd=1 arrives in 96 hours. Car at pos=2, spd=2 arrives in 49 hours. Car at pos=0, spd=4 arrives in 25 hours. Processing from closest: push 96.0, then 49.0 < 96.0 so push... wait, 49.0 < 96.0 means arrival is smaller, meaning pos=2 arrives sooner. 49.0 is not greater than 96.0, so it is absorbed. Then 25.0 is not greater than 96.0, absorbed again. Stack: [96.0]. One fleet. Matches the expected output.

Two cars, trailing arrives at exactly the same time: the condition is arrival > stack[-1], so equality triggers the else branch (absorb). The problem says if a car catches the fleet at the mile target it still counts. Correct.

All positions near 0, target is huge: no overflow risk. Arrival times are at most target / 1 = 10^6, a perfectly safe double.

Cars already sorted in descending order by input: the sort is still O(n log n). You cannot skip it because the input guarantees unique positions but not any particular order.

Why the stack is monotonically increasing

After the sweep, the stack contains arrival times in strictly increasing order from bottom to top. The bottom is the fleet closest to target (smallest arrival time). The top is the slowest fleet, farthest from target.

This monotone property is not incidental — it is the invariant you maintain. You only push when the new arrival time is strictly greater than the current top. Any new entry you push is larger than everything below it. The stack is a record of "fleet leaders that no car further back has been able to catch."

The pattern here is a monotone stack, but one where you do not need to pop anything. Every element stays once pushed. The stack size is the answer. This is a degenerate monotone stack — sometimes called a one-way monotone stack — because you only push, never pop.

What I would actually write

The brute-force simulation is not a realistic interview step. It is too messy and it fails obviously. I would go directly to the observation: sort by position descending, compute arrival times, run the stack sweep. The code is about 8 lines in Python.

The one thing that trips people up is the sort direction. Ascending is the natural default — you think "process cars in order from start to finish." Wrong direction. You need to process from closest-to-target to furthest, because a car can only be blocked by something between it and the finish line, not something behind it. Sort descending, or sort ascending and iterate in reverse.

The second thing that trips people is the comparison sign. You absorb when arrival <= top, not <. Missing the equality case means the problem's rule — "if a car catches the fleet at target, it still counts" — is violated. Cars with identical arrival times must collapse into one fleet.

For an interview, I would write the sort-plus-stack solution and justify it this way: "Arrival time summarises everything about a car's fate. Two cars form a fleet if and only if the trailing car's arrival time is no greater than the leading car's. So I sort by position, compute arrivals, and scan front-to-back maintaining a stack of distinct fleet leaders." That is the whole argument. Ten seconds to explain, eight lines to write.

Comparison table

Where this sits in the stack series

The stack series so far has covered Valid Parentheses (matching structure), and Evaluate Reverse Polish Notation (operand accumulation). Car Fleet adds a third pattern: using a stack not to track nesting or values, but to maintain a monotone sequence and count its length.

The arrival-time trick is the key transferable idea. Anytime you have objects racing toward a boundary, and later objects can only catch earlier objects (never pass them), you can collapse the simulation into an arrival-time comparison. The stack holds the distinct "uncatchable" groups.

Daily Temperatures (739) is the canonical monotone stack warm-up. You maintain a decreasing stack of temperatures and pop when you find a warmer day. Same structural idea: maintain a sequence with a monotone property, update it as you scan. The difference is that 739 pops elements (each element exits when dominated), while Car Fleet only pushes (each fleet leader stays).

Largest Rectangle in Histogram (84) is harder but the same family. The stack maintains indices of bars in increasing height order. Each bar is pushed when it extends the current run, popped when a shorter bar ends it. Again, a stack maintaining a monotone property over a linear scan.

Trapping Rain Water (42) uses a similar idea: process from boundaries inward, tracking the maximum seen so far as the constraint that determines how much water any position can hold. The "constraint from the leading element" logic is structurally the same as Car Fleet's "arrival time of the fleet ahead."

Online Stock Span (901) is perhaps the closest cousin. You have a series of prices, and for each day you want to know how many consecutive days (including today) the price was no greater. The stack stores spans of dominated days — same as Car Fleet stores absorbed cars. Worth doing next if this problem felt natural.