Car Fleet

Problem

Cars sit at different positions on a one-lane road, each with its own speed, all driving toward the same target. A car that catches up to a slower one ahead is stuck driving at that car's speed, forming a fleet. Count how many distinct fleets arrive at the target.

My notes

30 MIN00:00unlocks in 30:00

Signal

"Process items front-to-back, and each new item either merges into the current group or starts a new one" is a stack of running groups — process cars in order of position and compare each against the fleet currently ahead of it.

Approach

Sort cars by starting position, closest to the target first. For each car, compute the time it would take to reach the target alone: (target - position) / speed. Walking from closest to farthest, a car joins the fleet ahead of it if its own time is <= that fleet's time (it never actually passes); otherwise it's slower and becomes a new fleet leader. The count of fleet leaders is the answer — track it with a stack of arrival times, pushing only when a new (slower) leader appears.

Skeleton

cars = sorted(zip(position, speed), by position, descending)
times = []  # stack of fleet arrival times, one per fleet
for pos, spd in cars:
    t = (target - pos) / spd
    if not times or t > times.top:
        times.push(t)   # new, slower fleet
    # else: absorbed into the fleet ahead, no push
return len(times)

Solution

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    cars = sorted(zip(position, speed), key=lambda p: p[0], reverse=True)
    fleet_times: list[float] = []

    for pos, spd in cars:
        time_to_target = (target - pos) / spd
        if not fleet_times or time_to_target > fleet_times[-1]:
            fleet_times.append(time_to_target)
        # else: catches up to the fleet ahead, doesn't form a new one

    return len(fleet_times)

Complexity

O(n log n) time — dominated by the sort; the single pass after is O(n). O(n) space for the sorted pairs and the fleet-time stack.

Pitfalls

Sorting by position ascending and walking left-to-right silently breaks the logic — you must compare each car against the fleet ahead of it (closer to target), so process from closest-to-target outward.
Using >= instead of > when checking "does this car form a new fleet" would incorrectly split a fleet on an exact tie in arrival time.
The values are real numbers (division), not integers — comparing with == anywhere here is fragile; the algorithm only ever needs <=/>.

locked30:00 left