Car Fleet

MEDIUM✓ CHIP-TIMEDLC #853 — FULL STATEMENT ↗

The drill: Cars race to the same finish line at fixed speeds; a faster car stuck behind a slower one can never pass, so it slows to match and the two become one fleet. Count how many fleets cross the line.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A group of cars race toward the same finish-line position along a single lane, each starting at its own position with its own constant speed.

A faster car that catches up to a slower one ahead can never pass it — the lane is too narrow — so it's forced to slow down and travel at the slower car's pace from then on, and the two are considered one fleet for the rest of the trip.

The drill counts how many distinct fleets end up crossing the finish line, where a fleet can absorb more cars from behind but never splits apart once formed.

EX 01

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

→ 3

A MIX OF MERGES AND STANDALONE FLEETS

EX 02

target = 10 · position = [3] · speed = [3]

→ 1

MINIMUM SIZE, A SINGLE CAR

EX 03

target = 100 · position = [0, 2, 4] · speed = [4, 2, 1]

→ 1

EVERYONE CATCHES THE LONE FRONT CAR

field holds up to a few thousand cars
positions are distinct and speeds are strictly positive
a faster car merges into the fleet it catches, never passes it
answer is the count of fleets that reach the finish

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A car's fate depends only on how long it would take to reach the finish alone, and on whichever fleet is directly ahead of it — nothing farther ahead ever matters once that's decided.

HINT 2 THE STRUCTURE

Process cars from closest-to-target backward. If a car's own solo time is no greater than the time of the fleet immediately ahead, it catches up and merges into it; otherwise it starts a brand-new fleet.

HINT 3 ONE STEP FROM THE ANSWER

Sort by starting position descending, compute each car's solo (target − position) / speed, and push onto a stack only when that time is strictly greater than the stack's top. The stack's final size is the fleet count.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE MERGE SWEEPPATTERN · MONOTONIC TIME STACKtarget = 12 · sorted by position desc: (10,2) (8,4) (5,1) (3,3) (0,1)

p10 s2

p8 s4

p5 s1

p3 s3

p0 s1

FLEET STACK (solo arrival times)

— empty —

STEP 1

Target 12. Sort cars by position descending, then sweep once: a car merges into the fleet ahead unless its solo time is strictly greater — that starts a new fleet.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/car-fleet.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        stack = []  # solo arrival times of confirmed fleet leaders
        for p, s in cars:
            time = (target - p) / s
            if not stack or time > stack[-1]:
                stack.append(time)
        return len(stack)

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 9 LN

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        solo = [(target - p) / s for p, s in cars]
        fleets = 0
        for i in range(len(solo)):
            # rescan every car ahead of this one, from scratch, to see if it's a new leader
            is_leader = True
            for j in range(i):
                if solo[j] >= solo[i]:
                    is_leader = False
                    break
            if is_leader:
                fleets += 1
        return fleets

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

class 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, (x, y) -> position[y] - position[x]);
        Deque<Double> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int c = idx[i];
            double time = (double) (target - position[c]) / speed[c];
            if (stack.isEmpty() || time > stack.peek()) {
                stack.push(time);
            }
        }
        return stack.size();
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 19 LN

class 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, (x, y) -> position[y] - position[x]);
        double[] solo = new double[n];
        for (int i = 0; i < n; i++) {
            int c = idx[i];
            solo[i] = (double) (target - position[c]) / speed[c];
        }
        int fleets = 0;
        for (int i = 0; i < n; i++) {
            boolean isLeader = true;
            for (int j = 0; j < i; j++) {
                if (solo[j] >= solo[i]) {
                    isLeader = false;
                    break;
                }
            }
            if (isLeader) {
                fleets++;
            }
        }
        return fleets;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED