Problem overview
The method carFleet receives the target distance of a one-lane road and two vectors, position and speed. Car i starts at mile position[i] and drives at speed[i] miles per hour toward target. A car can't pass the car ahead. If it catches up, it slows down and drives on at the speed of the car in front, bumper to bumper. A group of cars driving together is a fleet, and a car alone is a fleet too. A car that catches a fleet exactly at target belongs to that fleet. The method returns the number of fleets that arrive.
In the first example, target = 12, position = [10, 8, 0, 5, 3] and speed = [2, 4, 1, 1, 3]. The car from mile 10 needs 1 hour and the car from mile 8 also needs 1 hour, so they arrive together: one fleet. The car from mile 5 needs 7 hours, and the car from mile 3 would need 3 but is held up behind it: a second fleet that arrives after 7 hours. The car from mile 0 needs 12 hours and never catches anyone: a third. The answer is 3.
Approach: sort by position, compare arrival times
Only the order of the cars on the road matters. Look at them from the one closest to target to the one farthest away. The closest car can never be blocked. If car i drove alone, it would arrive after (target - position[i]) / speed[i] hours.
Compare each car with the fleet just ahead of it. If the car would arrive no later than that fleet, it catches up with it, at the latest at the target, and joins it. If it would arrive strictly later, it never catches up, and it starts a new fleet that the cars behind it may still join. A fleet arrives when its leading car would arrive on its own, because that car was never slowed down.
The fleet just ahead of the next car is always the last one found, so a stack works: push a car when it starts a new fleet, and compare each new car only with the top. The answer is the size of the stack.
The sort costs O(n log n) and the pass after it costs O(n).
The trace for the first example, in the order the cars are visited:
| car (mile, speed) | alone | fleet ahead | result | fleets |
|---|---|---|---|---|
| 10, 2 | 2/2 h | none | new fleet | 1 |
| 8, 4 | 4/4 h | 2/2 h | joins | 1 |
| 5, 1 | 7/1 h | 2/2 h | new fleet | 2 |
| 3, 3 | 9/3 h | 7/1 h | joins | 2 |
| 0, 1 | 12/1 h | 7/1 h | new fleet | 3 |
Comparing times without dividing
The times are fractions, and equal times must compare as equal. The lesson avoids division. Since speeds are positive, (target - p1) / s1 > (target - p2) / s2 is equivalent to (target - p1) * s2 > (target - p2) * s1. Equal times then stay exactly equal. The condition is strict because a car that arrives at the same moment catches the fleet at the target and still counts as part of it.
Those products can reach 10^12 (a distance up to 10^6 times a speed up to 10^6), far more than a 32-bit int holds. The helper therefore does the multiplication in long long.
Step by step
- Store the car count,
position.size(), in anintnamedn. - Create
order, avector<int>of sizen. It will hold car numbers, so that sorting keeps each position paired with its speed: carorder[k]starts atposition[order[k]]and drives atspeed[order[k]]. - Fill it with a loop over
ifrom 0 ton - 1. - Set
order[i] = iinside the loop. - Sort by position, closest to the target first. The comparison lambda
[&](int a, int b) { return position[a] > position[b]; }returns true when caramust come first.[&]lets it readposition. - Create the stack
fleets, astack<int>holding for each fleet the number of its leading car. That car's number is all you need to know about the fleet. - Visit the cars in sorted order with a range-based
foroverorderand anint car. - Decide if the car starts a fleet. It does when the stack is empty or when
arrivesLater(target, position, speed, car, fleets.top())is true.||stops at the first true part, sotop()is only read when the stack isn't empty. - Push the car with
fleets.push(car): it leads a new fleet. A car that doesn't start a fleet joins the one on top, and nothing needs to be done. - Return
fleets.size(). Every car either started a fleet or joined one, so each fleet is on the stack exactly once. - Write the helper
arrivesLaterbelowcarFleet. It returns abooland takestarget,position,speed,carandlead. It answers whethercar, driving alone, arrives strictly later thanlead. - Compare the times with the cross-multiplied products, casting the first factor of each product to
long long.
The solution in C++
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
int n = position.size();
vector<int> order(n);
for (int i = 0; i < n; i++) {
order[i] = i;
}
sort(order.begin(), order.end(), [&](int a, int b) { return position[a] > position[b]; });
stack<int> fleets;
for (int car : order) {
if (fleets.empty() || arrivesLater(target, position, speed, car, fleets.top())) {
fleets.push(car);
}
}
return fleets.size();
}
bool arrivesLater(int target, vector<int>& position, vector<int>& speed, int car, int lead) {
return (long long) (target - position[car]) * speed[lead] > (long long) (target - position[lead]) * speed[car];
}
};
C++ details worth knowing:
- Where the cast sits. In
(long long) (target - position[car]) * speed[lead], the cast applies to the parenthesised difference only, and then the multiplication happens between along longand anint, which is done inlong long. Casting after the multiplication would be too late: withx = y = 1000000,(long long)(x * y)prints -727379968, while(long long)x * yprints 1000000000000. Signed overflow is undefined behaviour, so the first result is not something to rely on. - What goes wrong with
intproducts. Fortarget = 1000000,position = [0, 1]andspeed = [1000000, 1], the fast car at mile 0 reaches the target in 1 hour and the slow car ahead needs 999999 hours, so the answer is 1 fleet. With 32-bit products the second product, 999999 * 1000000, overflows, the comparison comes out wrong and the method returns 2. - Sorting indexes. Sorting
orderinstead of the positions keeps each speed attached to its position. The lambda capturespositionby reference with[&], so no copy is made. - Calling a member function defined later. Inside a class, a member function may call another one that is written below it. That is why
carFleetcan usearrivesLater. - The return type.
fleets.size()is unsigned and is converted to theintreturn value. The number of fleets is at mostn, so it fits.
Complexity
Time: O(n log n). Sorting the car numbers takes O(n log n). The pass over the sorted cars does constant work per car, so the sort is the larger part.
Space: O(n). The order vector and the stack each hold at most n numbers.
Edge cases and common mistakes
- One car. It is a fleet by itself: the answer is 1.
- Equal arrival times. A comparison with
>=instead of>would count a car that arrives together with the fleet ahead as a new fleet. In the first example, the cars from miles 10 and 8 both need 1 hour and form one fleet. - A fast car behind a slow one. For
target = 100,position = [0, 2, 4]andspeed = [4, 2, 1]every car ends up behind the slowest one, so there is one fleet. - Meeting exactly at the target. For
target = 10,position = [8, 0]andspeed = [1, 5]both cars need 2 hours, so the faster one reaches the slower one right at the target and the answer is 1. Withposition = [0, 5]andspeed = [1, 1]the cars never meet and the answer is 2. - Cars given in any order. The input is not sorted by position, so skipping the sort gives wrong answers. The first example is in no particular order.
- Dividing integers.
(target - position[i]) / speed[i]withintdrops the fraction, and different times could look equal. The cross-multiplied comparison is exact.
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 = [0, 4, 2],speed = [1, 2, 3]gives 2.target = 10,position = [6, 8],speed = [3, 2]gives 2.target = 10,position = [0, 5],speed = [1, 1]gives 2.target = 10,position = [8, 0],speed = [1, 5]gives 1.target = 1000000,position = [0, 1],speed = [1000000, 1]gives 1.
