Problem overview
The method carFleet receives a target (the mile where the road ends) and two lists, position and speed. Car i starts at mile position[i] and drives at speed[i] miles per hour. Cars can't pass each other. A car that catches up with a slower one has to slow down and drive on at the speed of the car in front, bumper to bumper. Cars driving together form a fleet, and a lone car is a fleet too. A car that catches up exactly at the target is part of that fleet. The method returns how many fleets arrive at the target.
For target = 12, position = [10, 8, 0, 5, 3] and speed = [2, 4, 1, 1, 3] the answer is 3:
- The cars at miles 10 and 8 would both arrive after 1 hour, so the one behind catches up at the target exactly. That is one fleet.
- The car at mile 5 (speed 1) would need 7 hours. The car at mile 3 (speed 3) would need 3, so it catches up and the two continue at speed 1. That is a second fleet.
- The car at mile 0 (speed 1) would need 12 hours and never catches anyone. That is a third fleet.
The lesson asks for O(n log n) time and O(n) extra space.
Approach: go from the front car backwards and compare arrival times
Only the order of the cars on the road matters, so look at them from the one closest to the target to the one farthest away. Driving alone, car i would arrive after (target - position[i]) / speed[i] hours. The car at the very front is never blocked. Every other car can only be held up by the cars ahead of it, and those were already handled.
A car that would arrive no later than the fleet just ahead of it catches up with that fleet, at the latest at the target, and joins it. A car that would arrive later never catches up, so it starts a new fleet, which the cars behind it may join. A fleet's arrival time is the time of the car that leads it, because that car was never slowed down.
That suggests a stack of fleets, each represented by its lead car. The fleet just ahead of the next car is always the one on top, and it is also the one that arrives last so far, so one comparison with the top is enough. A car that arrives later goes on the stack; otherwise it joins the top fleet and nothing changes. The answer is the size of the stack.
The same example, visited in order of position (cars 0, 1, 3, 4, 2):
| car | position | speed | alone, arrives after | result | fleet leaders afterwards |
|---|---|---|---|---|---|
| 0 | 10 | 2 | 1.0 h | new fleet | [0] |
| 1 | 8 | 4 | 1.0 h | joins | [0] |
| 3 | 5 | 1 | 7.0 h | new fleet | [0, 3] |
| 4 | 3 | 3 | 3.0 h | joins | [0, 3] |
| 2 | 0 | 1 | 12.0 h | new fleet | [0, 3, 2] |
Car 1 ties with car 0 at 1.0 hour, which counts as joining. The stack ends with three leaders, so the answer is 3.
Step by step
- Make the car numbers:
order = list(range(len(position))). Sorting the numbers rather than the positions keeps each car's position and speed together: carorder[k]starts atposition[order[k]]and drives atspeed[order[k]]. - Sort
orderby position, closest to the target first, withorder.sort(key=lambda car: position[car], reverse=True). - Create the empty list
fleets, the stack of lead cars. - Loop over
orderwith the variablecar. - Test for a new fleet: the stack is empty, or the car would arrive later than the top fleet, which the helper
arrivesLaterdecides. - Push the car with
fleets.append(car)when it starts a new fleet. Otherwise do nothing: it joined. - Return
len(fleets). - Write the helper
arrivesLaterbelowcarFleet, takingself, target, position, speed, car, lead. - Compare without dividing.
carwould arrive after(target - position[car]) / speed[car]hours andleadafter(target - position[lead]) / speed[lead]. Multiply both sides by the two positive speeds and compare(target - position[car]) * speed[lead]with(target - position[lead]) * speed[car]. The comparison must be strict: a car arriving at the same moment still belongs to the fleet.
The solution in Python
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
order = list(range(len(position)))
order.sort(key=lambda car: position[car], reverse=True)
fleets = []
for car in order:
if not fleets or self.arrivesLater(target, position, speed, car, fleets[-1]):
fleets.append(car)
return len(fleets)
def arrivesLater(self, target, position, speed, car, lead):
return (target - position[car]) * speed[lead] > (target - position[lead]) * speed[car]
Python details worth knowing:
sortwith a key.order.sort(...)sorts the list in place and returnsNone, which is why the code doesn't assign its result. Thekeyfunction receives each car number and returns the value to sort by:lambda car: position[car]is a one-line function doing exactly that.reverse=Trueputs the largest positions first.- Short-circuit
or. Innot fleets or ..., Python stops at the first true part. When the stack is empty,fleets[-1]is never evaluated, which would raise anIndexError. fleets[-1]is the last element of the list, the top of the stack.- Exact products. Python integers have no fixed size, so the products, up to about 10^12 here, can't overflow. In a language with 32-bit integers they would need a wider type.
- Methods calling methods. The helper is called as
self.arrivesLater(...), and its parameters get the values of the arguments in order afterself.
Complexity
Time: O(n log n). Sorting the car numbers is O(n log n). The loop does a constant amount of work per car (one comparison and at most one push), so it is O(n), and the sort is the larger part.
Space: O(n). The list order holds n numbers, and the stack holds at most n.
Edge cases and common mistakes
- A single car.
target = 10with one car returns 1. - A chain of catch-ups. For
target = 100,position = [0, 2, 4]andspeed = [4, 2, 1]every car is faster than the one ahead, but each ends up behind the slowest. The result is 1. - Ties. Equal arrival times mean one fleet, as the first example shows with cars 0 and 1. Using
>=in the helper would count a tied car as a new fleet: the first example would return 4 instead of 3. - Input in any order. The positions are not sorted in the input. Visiting the cars in input order breaks the stack logic. For
target = 10,position = [0, 4, 2]andspeed = [2, 1, 3]the answer is 1, but skipping the sort gives 2. - Sorting the positions alone. Sorting only
positionloses which speed belongs to which car. Sorting car numbers with a key keeps them together. - A fast car far behind. For
target = 10,position = [0, 5]andspeed = [5, 1], the car at mile 0 would arrive after 2 hours, before the car at mile 5, which needs 5. It catches up and joins, so the answer is 1. - A car that stays behind. For
target = 10,position = [6, 8]andspeed = [3, 2], the rear car needs 4/3 of an hour and the front car 1 hour. The rear car arrives later and never catches up, so the answer is 2. - Comparing against the wrong fleet. Only the top of the stack matters. It is the fleet that arrives last, and a car that arrives no later than it also arrives no later than any fleet below.
Testing
target = 12,position = [10, 8, 0, 5, 3],speed = [2, 4, 1, 1, 3]gives3.target = 10,position = [3],speed = [3]gives1.target = 100,position = [0, 2, 4],speed = [4, 2, 1]gives1.target = 10,position = [6, 8],speed = [3, 2]gives2.target = 10,position = [0, 4, 2],speed = [2, 1, 3]gives1.target = 10,position = [0, 5],speed = [5, 1]gives1.
