Problem overview
The function car_fleet receives a target (the distance in miles to the destination) and two vectors of the same length: position and speed. Car i starts at mile position[i] and drives at speed[i] miles per hour toward target. The road has one lane, so a car can never pass the one ahead. When a car catches up with a slower car, it slows to that car's speed and they drive on together. Such a group is a car fleet, and a car that drives alone is a fleet of one. A car that catches a fleet exactly at target still belongs to it. The function returns how many fleets reach target.
In the first example, target = 12, position = [10, 8, 0, 5, 3] and speed = [2, 4, 1, 1, 3]. The cars from miles 10 and 8 would both need 1 hour, so the car behind catches the front one exactly at the target: one fleet. The car from mile 5 would need 7 hours, and the car from mile 3 catches it at mile 6 and slows down to its speed: a second fleet. The car from mile 0 needs 12 hours and catches nobody: a third. The answer is 3.
The lesson asks for O(n log n) time and O(n) extra space.
Approach: sort by position and compare arrival times
Only the order of the cars on the road matters, so visit them from the one closest to the target to the one farthest away. If nothing slowed it down, car i would arrive after (target - position[i]) / speed[i] hours. The first car in this order is never blocked. Every later car is behind the cars already seen, and it meets one of two outcomes:
- It would arrive no later than the fleet just ahead. It catches up with that fleet, at the latest at the target, and joins it.
- It would arrive later. It never catches up, so it starts a new fleet, which cars further back may still join.
A fleet arrives when its lead car would arrive on its own, since that car was never slowed. So a stack of lead cars is enough. The fleet just ahead of the next car is always the one on top, and it is also the one that arrives last, so the car is compared with the top only. The answer is the size of the stack.
For the first example, the cars sorted by position, closest to the target first, are the car numbers [0, 1, 3, 4, 2], and their arrival times are [1.0, 1.0, 7.0, 3.0, 12.0]. Car 0 starts a fleet. Car 1 arrives at the same time, so it joins. Car 3 needs 7, more than 1, so it starts a fleet. Car 4 needs 3, no more than 7, so it joins. Car 2 needs 12, so it starts a third fleet.
Comparing times without dividing
The times are fractions, and equal times must count as equal, so the code avoids floating point. Because speeds are positive, (target - p1) / s1 > (target - p2) / s2 holds exactly when (target - p1) * s2 > (target - p2) * s1. Multiplying both sides by the two speeds removes the fractions and keeps the comparison the same.
Step by step
- Make the car numbers: a mutable
Vec<usize>namedorderfrom(0..position.len()).collect(). Sorting car numbers, not positions, keeps each position tied to its speed. - Sort
orderby position, largest first, withsort_byand the closure|&a, &b| position[b].cmp(&position[a]). Comparingbwithainstead ofawithbreverses the order. - Create the stack: an empty
Vec<usize>namedfleets. It holds the number of the lead car of each fleet found so far, and its last element is the top. - Loop over
&orderwith the pattern&car, which borrows the vector and copies each number out. - Decide whether this car starts a fleet. It does when the stack is empty, or when it would arrive later than the top fleet. The helper
arrives_lateranswers the second question, and||reads the top only when the stack isn't empty. - Push the car with
fleets.push(car). If the car doesn't start a fleet, it joins the top one and nothing changes. - Return the stack's size with
fleets.len() as i32, converting theusizeto the return type. - Write the helper
arrives_later. It takestarget, two borrowed slices&[i32]for the positions and speeds, the number of thecarand the number of theleadcar, and returns abool. It must be strict: a car that arrives at the same moment joins the fleet. - Compare with 64-bit products. Each factor is converted with
as i64before multiplying.
The solution in Rust
impl Solution {
fn car_fleet(target: i32, position: Vec<i32>, speed: Vec<i32>) -> i32 {
let mut order: Vec<usize> = (0..position.len()).collect();
order.sort_by(|&a, &b| position[b].cmp(&position[a]));
let mut fleets: Vec<usize> = Vec::new();
for &car in &order {
if fleets.is_empty() || Self::arrives_later(target, &position, &speed, car, *fleets.last().unwrap()) {
fleets.push(car);
}
}
fleets.len() as i32
}
fn arrives_later(target: i32, position: &[i32], speed: &[i32], car: usize, lead: usize) -> bool {
(target - position[car]) as i64 * speed[lead] as i64 > (target - position[lead]) as i64 * speed[car] as i64
}
}
The Rust details worth a closer look:
collect()needs a target type. The annotationVec<usize>tells it what to build. The range0..position.len()yieldsusizevalues, the type Rust uses for indexes.- The sort closure.
sort_bypasses references to two elements, and the pattern|&a, &b|copies the numbers out. The closure uses them to look up positions, andcmpreturns anOrdering. The positions are all different, so the order is fully determined. last().unwrap().last()returns anOption<&usize>,unwrap()takes out the reference and*copies the number.||stops at the first true part, sounwrapnever runs on an empty stack.- Slices as parameters. The helper takes
&[i32], so the call passes&position, a&Vec<i32>, which Rust converts to a slice automatically. The helper borrows the data and does not take it over. asbinds tighter than*. In(target - position[car]) as i64 * speed[lead] as i64, each operand is converted first and then the two 64-bit numbers are multiplied.- Why 64 bits. The products can reach about a trillion (10^12), far past the
i32maximum of about 2.1 billion. For example 1,000,000 times 999,999 is 999999000000 as ani64, while the same product computed with wrappingi32arithmetic is -728379968. An ordinaryi32multiplication of these two numbers gives the same -728379968 in a build with-O, and stops a debug build with the panicattempt to multiply with overflow. - The difference
target - position[car]stays ini32because positions are belowtargetand both are at most 1,000,000, so it can't overflow.
Complexity
Time: O(n log n). Sorting the car numbers is O(n log n). The loop does constant work per car, so sorting is the larger part.
Space: O(n). The vector order and the stack fleets hold at most n numbers each.
Edge cases and common mistakes
- A single car.
target = 10with one car at mile 3 returns 1: the stack is empty at the first car, so it starts a fleet. - A back car that arrives later. With
target = 10, positions[6, 8]and speeds[3, 2], the front car needs 1 hour and the back car needs 4/3 of an hour, so it never catches up and the answer is 2. Equal arrival times, as in the first example, count as one fleet, which is why the comparison is strictly greater. - Same speed, never meeting.
target = 10, positions[0, 5], speeds[1, 1]returns 2: the back car never gains on the front one. - A chain of catch-ups. With
target = 100, positions[0, 2, 4]and speeds[4, 2, 1], each car would arrive sooner than the one ahead, so each joins it and the answer is 1. - Unsorted input. Positions come in any order. In the first example the closest-to-target order is
[0, 1, 3, 4, 2], not[0, 1, 2, 3, 4]. - Floating-point division. Dividing and comparing
f64values can make two equal times look different. The integer products stay exact. - Using 32-bit products. They overflow on large inputs, as in the example above.
- Comparing with the wrong fleet. Only the top of the stack matters: it is the fleet directly ahead, and the one that arrives last.
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, 5],speed = [1, 1]gives2.target = 10,position = [0, 4, 2],speed = [2, 1, 3]gives1.target = 1000000,position = [0, 1],speed = [1000000, 999999]gives1.
