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)

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, since it inherits the leader’s time) and restarting after every merge until a full sweep changes nothing.

def carFleet(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 rule it out: at n = 10^5, n^2 = 10^10 operations is far too slow. The sort already costs O(n log n), and a single pass after it is enough.

Approach 2 — Sort + monotonic stack of arrival times

Blocking only ever delays a car, and a fleet’s arrival time is its leader’s unobstructed time: cars that join from behind do not slow the leader down. So process cars from the front of the road backwards. Car i merges into the fleet ahead when 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 of the stack. The stack stays strictly increasing, since each new fleet is slower to arrive than the one in front of it. That sorted-order invariant, maintained by refusing (or popping) violating pushes, is what makes this a monotonic stack.

def carFleet(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. The five cars collapse into three fleets by arrival time:

flowchart LR
    subgraph R["rear of road"]
      E["car pos 0"]
    end
    subgraph M["middle"]
      C["car pos 5"]
      D["car pos 3"]
    end
    subgraph F["front of road"]
      A["car pos 10"]
      B["car pos 8"]
    end
    R -->|arrives 12.0| M
    M -->|arrives 7.0| F
    F -->|arrives 1.0| T["target 12"]

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 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.

def carFleet(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 outcome (here, unobstructed arrival time), sort by the dimension that defines “ahead,” and sweep once with a monotonic stack. 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-style problems that are posed as simulations.