Car Fleet

Repeated frontmost scan

Fleet decisions must happen from the destination backward. Without sorting, you can repeatedly search every unused car for the greatest position, then process that car's solo arrival time.

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    used = [False] * len(position)
    fleet_times: list[float] = []
 
    for _ in position:
        front = -1
        for i in range(len(position)):
            if not used[i] and (front == -1 or position[i] > position[front]):
                front = i
 
        used[front] = True
        arrival = (target - position[front]) / speed[front]
        if not fleet_times or arrival > fleet_times[-1]:
            fleet_times.append(arrival)
 
    return len(fleet_times)

If a car's solo arrival is no later than the latest fleet's arrival, it catches that fleet before or at the destination. A later arrival means it remains behind as a new fleet.

Time O(n²) — finding the next frontmost car scans the remaining input each time. Space O(n) for the used markers and fleet times.

Sort + monotonic times

Pay for the road order once. Pair every position with its arrival time, sort positions from greatest to smallest, then make the same fleet decision in one pass.

The arrival times you keep form a monotonic stack — each stored time is strictly greater than the one before it. A time less than or equal to the top disappears into that existing fleet; a greater time starts a fleet that can't catch anything ahead.

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    cars = sorted(zip(position, speed), reverse=True)
    fleet_times: list[float] = []
 
    for start, velocity in cars:
        arrival = (target - start) / velocity
        if not fleet_times or arrival > fleet_times[-1]:
            fleet_times.append(arrival)
 
    return len(fleet_times)

The fractional comparison has an exact form too. For distances d1, d2 and positive speeds v1, v2, compare d1 * v2 with d2 * v1. The largest possible product here is 10^15, which fits a signed 64-bit integer and JavaScript's exact integer range. The test data also keeps unequal floating arrival times at least 10^-9 apart.

Time O(n log n) for sorting, followed by an O(n) scan. Space O(n) for the sorted cars and the time stack.