Problem overview
There are n cars on a one-lane road, all driving to the same destination, target miles from the start. Car i starts at mile position[i] and drives at speed[i] miles per hour. A car can never pass the car ahead of it. When it catches up with a slower car, it slows down and the two drive on together at the speed of the car in front. A group of cars driving together is a car fleet, a car driving alone is a fleet too, and a car that catches a fleet exactly at target belongs to that fleet. The method carFleet returns how many fleets arrive at target.
In the first example, target = 12, position = [10, 8, 0, 5, 3] and speed = [2, 4, 1, 1, 3]. The cars at miles 10 and 8 would both need 1 hour, so the second catches the first exactly at the target: one fleet. The cars at miles 5 and 3 meet and drive on together at speed 1: a second fleet. The car at mile 0 never catches anyone: a third fleet. The answer is 3.
Approach: sort by position, then compare arrival times
Simulating the road minute by minute is possible but messy. A simpler view comes from asking only one question about each car: how long would it take to reach the target if nothing slowed it down? For car i that is (target - position[i]) / speed[i] hours.
Now take the cars in order from the one closest to the target to the one farthest away. The closest car can never be blocked, so it leads the first fleet. For every later car, the only thing that matters is the fleet just ahead of it, because it can't pass anyone:
- If the car would arrive no later than that fleet, it catches up with it, at the latest at the target, and joins it. The fleet count does not change.
- If the car would arrive later, it never catches up. It starts a new fleet, and the cars behind it may join that one.
A fleet arrives at the time its lead car would arrive on its own, since that car was never slowed down. The fleet just ahead of the next car is also the one that arrives last so far, so it is the only one the next car needs to be compared with. A stack of fleets is therefore enough: the top is the most recently created fleet, and the answer is the size of the stack. Because the stack only ever needs the lead car of each fleet, it stores car numbers.
Running this on the first example, the cars sorted from the closest to the target are 0, 1, 3, 4 and 2, and the loop proceeds like this:
order [0,1,3,4,2]
car 0 pos 10 speed 2 alone time 1 new fleet stack [0]
car 1 pos 8 speed 4 alone time 1 joins stack [0]
car 3 pos 5 speed 1 alone time 7 new fleet stack [0,3]
car 4 pos 3 speed 3 alone time 3 joins stack [0,3]
car 2 pos 0 speed 1 alone time 12 new fleet stack [0,3,2]
Car 1 needs 1 hour, the same as car 0, so it joins. Car 4 needs 3 hours against the 7 of the fleet ahead, so it catches up and joins. Car 2 needs 12 hours against 7, so it starts the third fleet.
Step by step
- Make the car numbers.
orderis an array of the numbers 0 toposition.length - 1, built withArray.from({length: position.length}, (_, i) => i). Sorting car numbers, not positions, keeps each car attached to 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, soagoes first. - Create
fleets, an emptynumber[]used as a stack. It holds the lead car of every fleet found so far. - Loop over
orderwithfor...of, taking onecarat a time. - Decide whether the car starts a new fleet: when the stack is empty, or when the car would arrive later than the fleet on top. The helper
arrivesLateranswers that, and is written in the last steps. - Push the car onto the stack when it starts a fleet.
- Return
fleets.lengthafter the loop. - Write the helper
arrivesLaterwith the parameterstarget,position,speed,carandlead, returning aboolean. - Compare the two times without dividing.
(target - position[car]) * speed[lead]greater than(target - position[lead]) * speed[car]says the same as comparing the two times, since both speeds are positive.
The solution in TypeScript
class Solution {
carFleet(target: number, position: number[], speed: number[]): number {
const order: number[] = Array.from({length: position.length}, (_, i) => i);
order.sort((a, b) => position[b] - position[a]);
const fleets: number[] = [];
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: number, position: number[], speed: number[], car: number, lead: number): boolean {
return (target - position[car]) * speed[lead] > (target - position[lead]) * speed[car];
}
}
Details that matter in TypeScript:
- Sorting indexes.
order.sort(...)sorts the array in place and returns it. The comparison receives two car numbers and returns a number: negative putsafirst, positive putsbfirst. Subtractingposition[a]fromposition[b]sorts in descending order of position. - The comparison is not optional.
sort()with no comparator sorts values as strings:[10, 9, 1, 100].sort()gives[1, 10, 100, 9], while sorting with(a, b) => b - agives[100, 10, 9, 1]. - The underscore parameter. In
(_, i) => i, the first parameter is the element, which is not needed, and the name_says so.Array.fromwith a length object has no elements, so only the index is useful. - Cross-multiplying. Multiplying both sides of the comparison of the two fractions by the two speeds, which are positive, keeps the result and removes the division. A TypeScript
numberis a double that holds every integer up to 9,007,199,254,740,991 exactly. Here the products reach at most 1,000,000 times 1,000,000, which is a trillion, so they are exact and equal times compare as equal. - A method calling a method.
this.arrivesLaterneeds thethis., since methods of a class are not plain functions in scope. ||short-circuits. Whenfleets.length === 0is true, the second part is not evaluated, sofleets[fleets.length - 1]is never read from an empty stack.- Annotations are erased when the code is compiled to JavaScript, so the parameter types check nothing at run time.
Complexity
Time: O(n log n). Sorting the car numbers takes O(n log n). The loop then visits each car once, and each visit does a constant amount of work: one comparison of two products and at most one push. Sorting is the larger part.
Space: O(n). The order array holds n numbers and the stack holds at most n of them.
Edge cases and common mistakes
- A single car.
target = 10,position = [3],speed = [3]gives 1. - All cars merge. For
target = 100,position = [0, 2, 4]andspeed = [4, 2, 1], the fastest car is farthest back, but it can't pass, so it ends up in the same fleet with the other two. The answer is 1. - Equal arrival times. Two cars that would arrive at the same moment count as one fleet. That is why
arrivesLateruses a strict>: with>=,[10, 8]with speeds[2, 4]and target 12 would give 2 instead of 1. - Cars given out of order. The input is not sorted. For
target = 10,position = [0, 4, 2]andspeed = [2, 1, 3], the method returns 1. Skipping the sort would compare the wrong neighbours. - Same speed, different positions. Six cars at miles 3 to 8 with the same speed 4 never catch up with each other, so each is its own fleet: the answer is 6.
- Sorting the positions only. If you sort the
positionarray alone, each position loses its speed. Sort the car numbers and read both arrays through them. - Judging a car by its position alone. A car far behind may still catch up if it is fast enough. Only the arrival time matters.
Testing
target = 12,position = [10, 8, 0, 5, 3],speed = [2, 4, 1, 1, 3]gives 3.target = 10,position = [3],speed = [3]gives 1.target = 100,position = [0, 2, 4],speed = [4, 2, 1]gives 1.target = 10,position = [6, 8],speed = [3, 2]gives 2.target = 10,position = [0, 4, 2],speed = [2, 1, 3]gives 1.target = 10,position = [8, 3, 7, 4, 6, 5],speed = [4, 4, 4, 4, 4, 4]gives 6.
