A one-lane warehouse aisle runs AGVs toward a packing dock. Each bot has a start mile and a speed; the aisle is too narrow to pass. A faster bot that catches a slower one ahead must match that speed — from then on they are one convoy. Dispatch asked how many distinct convoys will arrive. The intern version stepped every bot through simulated time, merging when positions crossed. Twelve bots on a short aisle returned in milliseconds. A few thousand on the long pick-face were still comparing floating-point miles when the aisle planner timed out.

Car Fleet asks how many groups arrive when a faster car behind must join a slower one ahead. A catch is not a pass. After they meet they stay together, so the count is leaders, not cars. Simulating ticks uses that and still pays a physics loop. Nested “does i catch j?” uses that and still pays O(n²).

This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about a monotonic stack of arrival times so a new fleet is a strictly later arrival, not a restart of who meets whom. Same family as Daily Temperatures: there the stack holds indexes still waiting. Here it holds leaders still heading in. Do not re-solve the waits on this prompt.

The problem

Given a destination mile target and parallel arrays position and speed, cars drive a one-lane road toward the target and cannot pass. A faster car that catches a slower one ahead slows to that speed and they become one fleet; a meet exactly at target still counts as one. Return how many fleets arrive.

target = 12,  position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]  →  3
target = 10,  position = [3],              speed = [3]              →  1
target = 100, position = [0, 2, 4],        speed = [4, 2, 1]        →  1

In the first row, cars at 10 (speed 2) and 8 (speed 4) both need time 1 and meet at the dock: one fleet. Cars at 5 (speed 1) and 3 (speed 3) meet earlier and crawl in together. The car at 0 never catches anyone. Three fleets. The third row is the chain: everybody behind catches the slow car nearest the target, so one fleet.

Note: Positions are unique. Time to target is (target - position) / speed as a double. Equal time means they meet at the destination — still one fleet. The comparison is <=, not <.

Nested catch checks are the honest brute force

Sort closest to the target first, then for each car scan every car already closer; if this unimpeded time is <= any of those, it is not a new fleet. Correct. Quadratic.

int carFleetNested(int target, int[] position, int[] speed) {
    int n = position.length;
    int[][] cars = new int[n][2];
    for (int i = 0; i < n; i++) {
        cars[i][0] = position[i];
        cars[i][1] = speed[i];
    }
    Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0]));

    int fleets = 0;
    for (int i = 0; i < n; i++) {
        double time = (double) (target - cars[i][0]) / cars[i][1];
        boolean caught = false;
        for (int j = 0; j < i; j++) {
            double ahead = (double) (target - cars[j][0]) / cars[j][1];
            if (time <= ahead) {
                caught = true;
                break;
            }
        }
        if (!caught) {
            fleets++;
        }
    }
    return fleets;
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid a nested scan for a question a running leader already answers: does this car arrive strictly later than the slowest fleet already closer to the target? Tick-by-tick simulation is the other intern bill — same merges, a floating-point mess, and still the wrong complexity.

Sort from the target, stack of leader times

Sort by position descending — closest to target first — so when you look at a car, every fleet that could block it is already decided. Time to target is (target - pos) / speed. The stack holds arrival times of fleets that are still leaders. Walk that order.

  • If the stack is empty, this car is a fleet. Push its time.
  • If time > fleets.peek(), it never catches the leader ahead. New fleet. Push.
  • If time <= fleets.peek(), it catches that fleet and does not start a new one. Do not push. Do not pop.

You never pop because a farther car cannot dissolve a closer convoy; it can only join it. Daily Temperatures pops when a later day resolves an earlier wait. This walk pushes when a farther car fails to catch. Same “who is still a leader” idea; different payload. The stack of times is increasing: each new leader arrives later than the one in front.

Walk the first sample. Stack contents are fleet arrival times; the top is the leader just ahead.

target = 12
closest → farthest after sort:

pos 10  speed 2  time (12-10)/2 = 1
pos  8  speed 4  time (12-8)/4  = 1
pos  5  speed 1  time (12-5)/1  = 7
pos  3  speed 3  time (12-3)/3  = 3
pos  0  speed 1  time 12/1      = 12

pos 10  time=1    []      new fleet          [1]
pos  8  time=1    1<=1    catch, no push     [1]
pos  5  time=7    7>1     new fleet          [1, 7]
pos  3  time=3    3<=7    catch, no push     [1, 7]
pos  0  time=12   12>7    new fleet          [1, 7, 12]

fleets = 3

The two nearest cars meet at mile 12: one fleet. The car at 3 would arrive in time 3 if the road were empty, but the car at 5 needs time 7, so it joins that crawl. The car at 0 needs 12, which is later than 7, so it is its own fleet.

The Java is that walk. The stack stores times, not positions.

int carFleet(int target, int[] position, int[] speed) {
    int n = position.length;
    int[][] cars = new int[n][2];
    for (int i = 0; i < n; i++) {
        cars[i][0] = position[i];
        cars[i][1] = speed[i];
    }
    Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0]));

    Deque<Double> fleets = new ArrayDeque<>();
    for (int[] car : cars) {
        double time = (double) (target - car[0]) / car[1];
        if (fleets.isEmpty() || time > fleets.peek()) {
            fleets.push(time);
        }
    }
    return fleets.size();
}

Time is O(n log n) for the sort, then an O(n) walk — each car is considered once and pushed at most once. Space is O(n) for the pairs and the stack. Do not quote the nested O(n²) as the intended bill.

Cast before you divide. Integer division would turn (12-10)/2 into 1 by luck and (12-5)/3 into 2 by accident. Do not pop on a catch. The closer fleet is still on the road; joining it is “skip the push,” not “remove the leader.”

What interviewers usually poke next

  • A scalar instead of a stack. You only ever read the top, so a double leadTime and an int count are the same walk. The stack is how you name “leaders so far” at the board; the scalar is the production trim. Same O(n) after the sort.
  • Same monotonic family. Daily Temperatures holds waiting indexes, not fleet times. Do not re-solve the waits on this prompt.
  • Later hard. Largest Rectangle in Histogram is the next index-stack problem in this family. Name it. Do not solve it here.
  • Sort the other way. Farthest first is the same O(n log n) and easier to botch which time is still the leader. Prefer closest-first unless they ask you to flip it.
  • Collision times, not a count. “When does each car catch the next one?” is a different prompt (Car Fleet II). Same road, new stack of collisions. Do not rewrite this method into that one.

You are done with this problem when you can walk [10, 8, 0, 5, 3] out loud, push 1, skip the equal 1, push 7, skip 3, push 12, and say why meeting at the target is still one fleet.