There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.
You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.
A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.
A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.
If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.
Return the number of car fleets that will arrive at the destination.
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
target.target.Example 2:
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation:
There is only one car, hence there is only one fleet.Example 3:
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
target.Constraints:
n == position.length == speed.length1 <= n <= 1050 < target <= 1060 <= position[i] < targetposition are unique.0 < speed[i] <= 106In #853 Car Fleet, cars start at different positions with different speeds and move toward a target. The key observation is that a faster car behind may eventually catch up to a slower car ahead, forming a fleet that travels together at the slower car's speed.
A common strategy is to sort cars by position in descending order so you process the car closest to the target first. For each car, compute the time = (target - position) / speed needed to reach the destination. While scanning from front to back, compare each car’s arrival time with the previous fleet’s time.
If a car reaches the target later than the fleet ahead, it becomes a new fleet. Otherwise, it merges with the fleet in front. This pattern can be implemented using a monotonic stack or simply by tracking the latest fleet arrival time.
The dominant cost comes from sorting the cars, giving a time complexity of O(n log n), while the traversal is linear. Space usage is O(n) depending on whether a stack or auxiliary structures are used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Fleet Time Tracking | O(n log n) | O(1) to O(n) |
| Sorting + Monotonic Stack | O(n log n) | O(n) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Car Fleet is a popular medium-level interview problem and has appeared in coding interviews at major tech companies. It tests understanding of sorting, greedy thinking, and stack-like patterns.
The optimal approach is to sort cars by position in descending order and compute the time each car takes to reach the target. By scanning from the car closest to the target, you track fleet arrival times and merge cars that catch up. Sorting dominates the runtime, giving O(n log n) complexity.
Sorting ensures we process cars starting from the one closest to the target. This order makes it easy to determine whether a car behind will catch up to the fleet ahead before reaching the destination.
A stack or monotonic stack is commonly used to track fleet arrival times. It helps determine whether a new car forms a new fleet or merges with the fleet ahead based on its time to reach the target.