Problem overview
Cars drive on a one-lane road toward a target mile. The method carFleet(target, position, speed) receives two arrays: car i starts at mile position[i] and drives at speed[i] miles per hour. A car can't pass the one ahead of it. When it catches up, it slows to the speed of the car in front and the two drive on together. A group driving together is a fleet, a car on its own is a fleet too, and a car that reaches a fleet exactly at the target belongs to it. The function returns the number of fleets that arrive.
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 need 1 hour, so they form one fleet. The cars at miles 5 and 3 meet at mile 6 and drive on at speed 1, a second fleet. The car at mile 0 would need 12 hours and never catches anyone, a third fleet. With a single car, as in target = 10, position = [3], speed = [3], the answer is 1. With target = 100, position = [0, 2, 4] and speed = [4, 2, 1], each car catches the next and all three end up as one fleet.
The statement asks for O(n log n) time and O(n) extra space.
Approach: sort by position, then compare arrival times
Simulating the road mile by mile, or hour by hour, would be awkward, because cars merge at fractional moments. The shortcut is to ask only when each car would arrive if nothing slowed it down: (target - position[i]) / speed[i] hours.
Look at the cars from the one closest to the target to the one farthest. The closest car can never be blocked, so it leads a fleet. Now take the next car back and compare its solo arrival time with the fleet just ahead:
- If it would arrive no later, it catches up with that fleet by the target at the latest, and it joins the fleet.
- If it would arrive later, it can never reach that fleet, and it leads a new fleet that the cars behind it may still join.
A fleet arrives when the car that leads it would arrive on its own, because that car was never slowed down. So it is enough to keep one number per fleet, the lead car, on a stack. The fleet just ahead of the next car is always the top of the stack, and it is also the one that arrives last. The answer is the size of the stack at the end.
For the first example, the cars from closest to farthest, with their solo arrival times in hours, are:
mile 10: 1
mile 8: 1
mile 5: 7
mile 3: 3
mile 0: 12
Mile 10 starts a fleet. Mile 8 (1 hour) is not later than the top (1 hour), so it joins. Mile 5 (7 hours) is later than 1, so it starts a second fleet. Mile 3 (3 hours) is not later than 7, so it joins that one. Mile 0 (12 hours) is later than 7 and starts a third fleet.
Step by step
- Make an array of car numbers,
order, holding 0 toposition.length - 1.Array.fromwith a length and an arrow function fills slotiwithi. Sorting the car numbers instead of the positions keeps each position paired with its speed. - Sort
orderby position, closest to the target first, with the comparison(a, b) => position[b] - position[a]. It is negative when carais closer to the target, which puts it first. - Create
fleets, an empty array used as a stack of lead car numbers. - Loop over
orderwithfor...of, one car at a time. - Test whether the car starts a new fleet. It does when the stack is empty, or when it would arrive later than the fleet on top. The helper
arrivesLateranswers the second question. Because||stops at the first true part, the top is only read when the stack has something in it. - Push the car when it starts a fleet. A car that joins a fleet needs no action.
- Return
fleets.length. Every car either started a fleet or joined one, so the stack holds each fleet once. - Declare the helper
arrivesLater(target, position, speed, car, lead)as a method of the class. It reports whethercar, driving alone, arrives strictly later thanlead. - Compare the times without dividing. The time of
caris greater than the time ofleadexactly when(target - position[car]) * speed[lead]is greater than(target - position[lead]) * speed[car], because speeds are positive. The comparison is strict: a car that ties arrives together with the fleet and belongs to it.
The solution in JavaScript
class Solution {
carFleet(target, position, speed) {
const order = Array.from({length: position.length}, (_, i) => i);
order.sort((a, b) => position[b] - position[a]);
const fleets = [];
for (const car of order) {
if (fleets.length === 0 || this.arrivesLater(target, position, speed, car, fleets[fleets.length - 1])) {
fleets.push(car);
}
}
return fleets.length;
}
arrivesLater(target, position, speed, car, lead) {
return (target - position[car]) * speed[lead] > (target - position[lead]) * speed[car];
}
}
JavaScript details worth knowing:
- Numbers are doubles, and that is enough here. Each product is at most about 1,000,000 times 1,000,000, which is 1,000,000,000,000. A double holds whole numbers exactly up to 9,007,199,254,740,991 (2 to the power 53, minus 1), so these products are exact and no
BigIntis needed. - Why not divide? Division produces fractions, and floating-point fractions can be slightly off:
0.1 + 0.2 === 0.3isfalsein JavaScript. A tie between two arrival times has to stay a tie, so the lesson compares whole-number products instead. sortneeds a comparator. Without one,sortturns the elements into strings:[5, 10, 0, 3].sort()gives[0, 10, 3, 5]. With the comparator(a, b) => b - athe result is[10, 5, 3, 0]. The comparator here subtracts positions, which are plain numbers.- It sorts car numbers, not positions.
order.sort(...)sorts in place and returns the same array. The comparator readspositionthrough the car numbers, so the originalpositionandspeedarrays are never reordered. - A method calling a method. Inside the class,
carFleetcalls the helper asthis.arrivesLater(...). Writing justarrivesLater(...)would look for a variable with that name and fail.
Complexity
Time: O(n log n). Sorting the car numbers takes O(n log n). The loop visits each car once and does constant work: one comparison and at most one push. Sorting is the larger part.
Space: O(n). order holds n numbers and fleets at most n.
Edge cases and common mistakes
- One car. The stack is empty, the car is pushed, and the answer is 1.
- Cars that tie at the target. With
target = 10,position = [0, 5]andspeed = [2, 1], both would need 5 hours, and the result is 1. A>=in the helper would count 2. - A faster car behind that catches up.
position = [0, 5],speed = [3, 1]withtarget = 10gives 1: the rear car would need about 3.3 hours and the front one 5. - Cars at the same speed.
position = [5, 0],speed = [1, 1]withtarget = 10gives 2. The rear car never gains on the front one. - Input not in order. The positions are not sorted in the input. Skipping the sort gives wrong answers.
- Comparing with the wrong fleet. A car should only be compared with the fleet immediately ahead, the top of the stack. Fleets further down arrive earlier and are irrelevant.
- Sorting positions on their own. If you sort a copy of
position, the speeds no longer line up with it. Sort the indexes.
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 = [0, 5],speed = [2, 1]gives1.target = 10,position = [5, 0],speed = [1, 1]gives2.target = 10,position = [0, 5],speed = [3, 1]gives1.
