DSA problem
Car Fleet
There are n cars going to the same destination along a one-lane road. The destination is target miles away. You are given two integer arrays position and speed, both of length n, where position[i] is the position of the i-th car and speed[i] is the speed of the i-th car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and then drive bumper-to-bumper at the same speed. The pair of cars then becomes a single car fleet that travels at the slower car's pace. Note that a single car is also considered a car fleet, and a car that catches up exactly at the target is still considered the same fleet.
Return the number of car fleets that will arrive at the destination. The key insight is that a slower car ahead caps the speed of any faster car behind it: time-to-target only matters in non-decreasing order from the closest-to-target car backward.
The optimal approach sorts cars by position in descending order (closest to the target first) and computes each car's time-to-target as (target - position) / speed. We then walk left to right and push each time onto a stack only if it is strictly greater than the current top — meaning this car cannot catch up to the fleet ahead before reaching the target, so it starts its own fleet. Otherwise it will catch up and merge into the existing fleet, so we don't push. The final stack size is the fleet count. Sorting is O(n log n) and the walk is O(n), so the total is O(n log n).
Examples
target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]3target = 10, position = [3], speed = [3]1target = 100, position = [0,2,4], speed = [4,2,1]1Constraints
- n == position.length == speed.length
- 1 <= n <= 10^5
- 0 < target <= 10^6
- 0 <= position[i] < target
- All values of position[i] are unique.
- 0 < speed[i] <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.