Car Fleet
Problem
n cars drive toward a target at position target. Each car has a position and speed. A faster car bumping into a slower one ahead joins it into a fleet at the slower speed. Return the number of fleets that reach the target.
target=12, position=[10,8,0,5,3], speed=[2,4,1,1,3]3def carFleet(target, position, speed):
cars = sorted(zip(position, speed), reverse=True)
stack = []
for p, s in cars:
t = (target - p) / s
if not stack or t > stack[-1]:
stack.append(t)
return len(stack)function carFleet(target, position, speed) {
const n = position.length;
const cars = position.map((p, i) => [p, speed[i]]).sort((a, b) => b[0] - a[0]);
const stack = [];
for (const [p, s] of cars) {
const t = (target - p) / s;
if (stack.length === 0 || t > stack[stack.length - 1]) stack.push(t);
}
return stack.length;
}class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> position[b] - position[a]);
Deque<Double> stack = new ArrayDeque<>();
for (int i : idx) {
double t = (double)(target - position[i]) / speed[i];
if (stack.isEmpty() || t > stack.peek()) stack.push(t);
}
return stack.size();
}
}int carFleet(int target, vector<int>& position, vector<int>& speed) {
int n = (int)position.size();
vector<pair<int, int>> cars(n);
for (int i = 0; i < n; i++) cars[i] = {position[i], speed[i]};
sort(cars.begin(), cars.end(), greater<>());
vector<double> st;
for (auto& [p, s] : cars) {
double t = (double)(target - p) / s;
if (st.empty() || t > st.back()) st.push_back(t);
}
return (int)st.size();
}Explanation
The big idea: a faster car can never pass a slower car ahead of it — it just catches up and they merge into one fleet moving at the slower speed. So we care about which cars end up grouped together by the time they reach the target.
First we sort the cars by position descending, so we process the car closest to the target first. For each car we compute its arrival time t = (target - position) / speed — how long it would take to reach the target if nothing blocked it.
We keep a stack of arrival times of the fleets ahead. For the current car, if its time t is greater than the time on top of the stack, it arrives later (it is slower and cannot catch the fleet ahead), so it starts a new fleet and we push t. If its time is not greater, it catches the fleet ahead and merges in (we do nothing).
The answer is simply the number of items left on the stack — that is the count of distinct fleets.
Example: target = 12, cars sorted by position give arrival times like 1, 1, 3, .... A car arriving at the same or earlier time than the fleet ahead joins it; only cars that arrive strictly later become new fleets, and counting those gives 3.