Pattern visualizer
Car Fleet
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. 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?.
Sort nearest-to-target first, keep a monotonic stack of arrival times
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.
1FUNCTION carFleet(target, position, speed)2 cars <- PAIRS(position, speed) SORTED BY position DESCENDING3 stack <- EMPTY4 FOR i <- 0 TO LENGTH(cars) - 15 t <- (target - cars[i].pos) / cars[i].speed6 IF stack IS EMPTY OR t > TOP(stack) THEN7 APPEND t TO stack8 RETURN LENGTH(stack)
← / → step · space play · Home restart