LeetCode #853 Medium

Car Fleet

Cars at given positions and speeds drive toward a target; a faster car catching a slower one joins its fleet at the slower speed. Return the number of fleets that arrive.

stacksortinggreedy

Open on LeetCode ↗

02

Intuition

💡

It feels natural to walk the cars from the back of the line forward, in the order they're given, but a car can only be blocked by one ahead of it toward the target — so you must process from closest-to-target backwards, or the fleet a car might join hasn't been decided yet. Compute each car's solo arrival time, (target - position) / speed, using true division; integer division truncates two close arrival times into looking equal and silently merges fleets that should stay separate. A car merges into the fleet ahead exactly when its arrival time is no later than that fleet's, so sweep with a running maximum: any time that exceeds the current maximum starts a new fleet.

03

Approach

1

Reduce each car to a single number

Positions and speeds together are awkward, but arrival time (target - position) / speed captures everything that matters. Two cars are in the same fleet exactly when the one behind would otherwise arrive no later than the one ahead.

2

Sort by position descending

Process from the car nearest the target backwards. Only cars ahead can block you, so this order means the fleet you might join has already been decided by the time you are considered.

3

Sweep with a running max

Keep slowest, the arrival time of the fleet currently ahead. If the next car's time is greater, it never catches up — it forms a new fleet, so increment the count and set slowest to its time. Otherwise it merges and changes nothing. Sorting dominates at O(n log n), with O(n) space; a stack is a common alternative formulation, but the running max is the same idea with less machinery.

04

Solution & live demo

python

▶1class Solution:
▶2    def carFleet(self, target, position, speed):
▶3        cars = sorted(zip(position, speed), reverse=True)
▶4        fleets = 0
▶5        slowest = 0.0
▶6        for p, s in cars:
▶7            t = (target - p) / s
▶8            if t > slowest:
▶9                fleets += 1
▶10                slowest = t
▶11            # else: catches the fleet ahead
▶12        return fleets

05

Edge cases

Single car

It is its own fleet, so the answer is 1.

All cars at the same speed

None ever catches another, so every car is its own fleet.

Equal arrival times

They arrive together and count as one fleet, so the comparison must be strict > for a new fleet.

Integer division

Arrival times need to be floats — truncating can merge fleets that should stay separate.

06

Complexity

Time

O(n log n)

Space

O(n)

Sorting dominates; the sweep is a single running maximum.