Stack · 106Medium
Car Fleet
Cars are at various positions heading to the same target, each with its own speed. A faster car catches a slower one and they travel on together as a fleet at the slower speed. Return how many fleets arrive at the destination.
Constraints
- n == position.length == speed.length
- 1 <= n <= 10^5
- 0 < target <= 10^6, 0 <= position[i] < target
- All positions are unique.
Examples
carFleet(12, [10,8,0,5,3], [2,4,1,1,3]) -> 3 carFleet(10, [3], [3]) -> 1 carFleet(100, [0, 2, 4], [4, 2, 1]) -> 1 carFleet(10, [0, 5], [1, 1]) -> 2 // equal speeds never catch up carFleet(12, [0, 2, 4], [1, 2, 3]) -> 3 // nobody catches anybody carFleet(10, [0, 4, 2], [2, 1, 3]) -> 1 // everyone merges behind the slowest
Edge cases
- A single car is one fleet.
- Cars that merge exactly AT the target still count as one fleet.
- Cars behind can never overtake — only catch up.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — simulate the positions over time and detect merges step by step.
- Target
- O(n log n) time — sort by position descending, compute each car's arrival time, and count how many times a new maximum arrival time appears.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/04-stack/106-car-fleet.js ./practice c 106