Car Fleet

Problem

n cars drive along a one-lane road toward a destination at mile target. Car i starts at mile position[i] (all starts distinct) and drives at speed[i] miles per hour. A car can never pass the car ahead of it: if it catches up, it slows to match and the two travel bumper-to-bumper as a single fleet from then on. A lone car is a fleet of one, and a car that catches another exactly at the target line still counts as part of that fleet.

Return how many fleets cross the target line.

Examples

• target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3] → 3 — the cars at 10 and 8 meet at mile 12 (one fleet); the car at 0 never catches anyone (one fleet); the cars at 5 and 3 meet at mile 6 and finish together (one fleet).
• target = 10, position = [3], speed = [3] → 1 — a single car is a single fleet.
• target = 100, position = [0, 2, 4], speed = [4, 2, 1] → 1 — the fastest car is last; everyone piles into the slow leader before mile 100.

Constraints

• 1 <= n <= 10^5
• 0 < target <= 10^6, 0 <= position[i] < target, all position[i] distinct
• 0 < speed[i] <= 10^6

n = 10^5 rules out quadratic re-simulation; the expected solution is sort plus one linear pass — O(n log n).

Think about it first

TL;DR

Sort by position descending, one pass over unobstructed arrival times with a monotonic stack — O(n log n) time, O(n) space (O(1) extra with a counter).

Approach 1 — Brute force (repeated merging)

Naive intuition: compute every car’s unobstructed arrival time, order cars front-to-back, then repeatedly sweep the list merging any car whose time is <= the fleet directly ahead (delete it — it inherits the leader’s time), restarting after every merge until a sweep changes nothing.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)   # front of road first
        times = [(target - p) / s for p, s in cars]
        merged = True
        while merged:
            merged = False
            for i in range(1, len(times)):
                if times[i] <= times[i - 1]:    # catches the fleet ahead
                    times[i : i + 1] = []       # joins it; leader's time stands
                    merged = True
                    break
        return len(times)

Complexity: O(n^2) time (up to n merges, each preceded by an O(n) sweep and O(n) deletion), O(n) space.

Why the constraints kill it: n = 10^5 makes n^2 = 10^10 operations — hopeless; the sort already costs O(n log n), and one pass after it is enough.

Approach 2 — Sort + monotonic stack of arrival times

The insight: blocking only ever delays a car, and a fleet’s arrival time is its leader’s unobstructed time — cars that join from behind don’t slow the leader down. So process cars from the front of the road backwards: car i merges into the fleet ahead iff its own unobstructed time (target - pos) / spd is <= that fleet’s time; otherwise it leads a new fleet. Keeping fleet times on a stack makes “the fleet ahead” the top; the stack stays strictly increasing (each new fleet is slower to arrive than the one in front of it), which makes this a monotonic stack — a stack whose invariant is sorted order, maintained by refusing (or popping) violating pushes.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        pairs = sorted(zip(position, speed), reverse=True)  # closest to target first
        stack: list[float] = []                             # fleet arrival times
        for pos, spd in pairs:
            time = (target - pos) / spd
            if not stack or time > stack[-1]:
                stack.append(time)          # can't catch the fleet ahead: new fleet
            # else: merges into the fleet on top; its time is absorbed
        return len(stack)

Walkthrough on target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3] — sorted front-first the (pos, spd) pairs are (10,2), (8,4), (5,1), (3,3), (0,1):

Stack size 3 → 3 fleets, matching the example.

Complexity: O(n log n) time (the sort dominates; the pass is O(n)), O(n) space for the sorted pairs and stack.

Approach 3 — Sort + single variable (drop the stack)

The insight: the pass above never pops and only ever compares against the top — so the whole stack can be replaced by one variable holding the slowest fleet time seen so far, plus a counter.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        order = sorted(range(len(position)), key=lambda i: -position[i])
        fleets = 0
        slowest = -1.0                       # arrival time of the rear-most fleet
        for i in order:
            time = (target - position[i]) / speed[i]
            if time > slowest:               # new fleet forms behind everything
                fleets += 1
                slowest = time
        return fleets

Walkthrough (same example): times arrive as 1.0, 1.0, 7.0, 3.0, 12.0; slowest moves −1 → 1.0 → (skip) → 7.0 → (skip) → 12.0, incrementing fleets three times → 3.

Complexity: O(n log n) time, O(n) for the sort order but O(1) extra working space beyond it.

Common pitfalls

• Strict vs non-strict comparison: a car that arrives at exactly the leader’s time (time == top) joins that fleet — pushing on >= overcounts fleets.
• Sorting direction confusion: you must process from the car nearest the target backwards; front cars are unaffected by cars behind them, which is what makes one pass valid.
• Integer division: (target - pos) / spd must stay a float; // silently merges fleets that shouldn’t merge.
• Forgetting speeds don’t matter after merging: a fast car that joins a fleet never “escapes” later — don’t try to re-simulate.

Pattern takeaway

Convert each item to the single number that decides its fate (here, unobstructed arrival time), sort by the dimension that defines “ahead,” and sweep once with a monotonic stack — and when the sweep only ever looks at the top without popping, collapse the stack to one variable. “Sort, then monotonic one-pass” is the standard shape for interval-merge-like problems dressed up as simulations.