LeetCode 853: Car Fleet — Step-by-Step Visual Trace

Medium — Array | Stack | Sorting | Greedy

The Problem

Given cars at different positions with different speeds all heading to the same target, determine how many car fleets will arrive at the target. Cars form a fleet when a faster car catches up to a slower car ahead.

Approach

Sort cars by position in descending order, then calculate each car’s arrival time. A new fleet forms when a car takes longer to reach the target than the previous car, since it won’t catch up to form a combined fleet.

Time: O(n log n) · Space: O(n)

Code

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        fleets = 0
        prev_time = -1.0

        for pos, spd in cars:
            time = (target - pos) / spd
            if time > prev_time:
                fleets += 1
                prev_time = time

        return fleets

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments