Car Fleet

Sort nearest-to-target first, keep a monotonic stack of arrival times

time O(n log n)space O(n)

Positions and speeds are a distraction; convert every car to the single number that decides everything — how long it would take to reach the target alone. Sort the cars so the one nearest the target comes first, because that car has nothing in front of it and its arrival time is final. Then walk backwards through traffic: a car whose solo time is at most the time of the fleet already ahead must run into it, so it is absorbed and changes nothing. Only a car SLOWER than everything ahead survives as its own fleet, and it becomes the new obstacle for everyone behind. The surviving times form a strictly increasing stack, and its height is the answer.

Details

Animated on: target = 12, position = [3, 10, 0, 8, 5, 4], speed = [3, 2, 1, 4, 1, 2] — cars cannot pass, so a faster car that catches a slower one joins its fleet. How many fleets reach the target?

Problem:Car FleetMedium

Sort nearest-to-target first, keep a monotonic stack of arrival times

step 1 / 10

p3 s3

[0]

p10 s2

[1]

p0 s1

[2]

p8 s4

[3]

p5 s1

[4]

p4 s2

[5]

target = 12, 6 cars given in arbitrary order. A car can never overtake, so the only thing that can slow a car down is a car AHEAD of it — which means the input order is useless and position order is everything.

Pseudocode

1FUNCTION carFleet(target, position, speed)
2  cars <- PAIRS(position, speed) SORTED BY position DESCENDING
3  stack <- EMPTY
4  FOR i <- 0 TO LENGTH(cars) - 1
5    t <- (target - cars[i].pos) / cars[i].speed
6    IF stack IS EMPTY OR t > TOP(stack) THEN
7      APPEND t TO stack
8  RETURN LENGTH(stack)

← / → step · space play · Home restart

Every step in words

Show all 10 steps

target = 12, 6 cars given in arbitrary order. A car can never overtake, so the only thing that can slow a car down is a car AHEAD of it — which means the input order is useless and position order is everything.
Sorted by position descending: 10, 8, 5, 4, 3, 0. Cell 0 is the car closest to the target, so nothing is ever in ITS way — scanning left to right means every car is examined after the traffic in front of it is already resolved.
Each car's solo arrival time is (12 - pos) / speed: p10 takes 1, p8 takes 1, p5 takes 7, p4 takes 4, p3 takes 3, p0 takes 12. Comparing times instead of positions is the trick — a car catches the one ahead exactly when it would otherwise arrive no later.
p10 is the front car with nothing ahead of it, so it arrives at t=1 unobstructed. Push 1 — the stack now holds one fleet.
p8 would arrive at t=1, exactly the fleet leader's t=1 — it touches the car ahead right at the line, which still counts as caught. Nothing is pushed, so the fleet count stays 1.
p5 needs t=7, which is LATER than the fleet ahead at t=1. It never closes the gap, so it can never merge — and because it is now the slowest thing on the road, everything behind it will pile up on IT. Push 7: 2 fleets so far.
p4 would arrive at t=4, SOONER than the fleet ahead at t=7, so it runs into that fleet before the target and is stuck behind it at t=7. Nothing is pushed — it is absorbed, and the fleet count stays 2.
p3 would arrive at t=3, SOONER than the fleet ahead at t=7, so it runs into that fleet before the target and is stuck behind it at t=7. Nothing is pushed — it is absorbed, and the fleet count stays 2.
p0 needs t=12, which is LATER than the fleet ahead at t=7. It never closes the gap, so it can never merge — and because it is now the slowest thing on the road, everything behind it will pile up on IT. Push 12: 3 fleets so far.
Every car classified. The stack holds 3 arrival times (1, 7, 12), one per fleet, and it is strictly increasing by construction — each highlighted leader is a car nothing ahead of it could hold back. Answer: 3 fleets.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Car Fleet in the editor All Stack problems Back to roadmap