Car Fleet

Cars on a one-lane road, each with a position and speed, all headed to the same target. A car can never pass the one ahead of it; once it catches up, both continue as a fleet at the leader's speed. Count how many fleets arrive at the target.

The key insight: only the car in front constrains the ones behind it. Sort cars by position (closest to target first), then compute each car's time to target: (target - position) / speed. A car behind forms a new fleet only if its arrival time exceeds the fleet ahead's — otherwise it catches up before the target. A monotonic stack scanning from front to back counts fleets: push times, and pop any time that is not greater than the time before it, since the trailing car merges into the fleet ahead.

Approach in steps:

1. Sort (position, speed) pairs descending by position.
2. Compute arrival time for each car.
3. Walk times; count how many are strictly greater than the max time seen ahead.

def carFleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    stack = []
    for pos, spd in cars:
        t = (target - pos) / spd
        if not stack or t > stack[-1]:
            stack.append(t)
    return len(stack)

Time is O(n log n) — dominated by the sort — with O(n) space.

Trickiest edge case: exact ties. Two cars arriving at the target in exactly the same time form one fleet — the > comparison (not >=) treats equal times as a merge. Floating point is exact enough here since equal times are equal fractions of the same integer math in practice, but the strict comparison is what keeps ties from becoming two fleets.