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] <= 106Problem Overview: You are given the position and speed of multiple cars driving toward a target. A faster car cannot pass a slower one ahead of it; instead, it joins that car and forms a fleet that travels at the slower speed. The task is to compute how many distinct fleets will arrive at the target.
Approach 1: Sorting and Time Calculation (O(n log n) time, O(1) space)
The key idea is to process cars from closest to the target to farthest. First, pair each car's position with its speed and sort the cars by position in descending order using sorting. For each car, compute the time needed to reach the target using (target - position) / speed. As you iterate through the sorted list, track the maximum arrival time seen so far. If the current car's time is greater than that maximum, it cannot catch the fleet ahead and forms a new fleet. Otherwise, it merges into the fleet in front.
This works because a car behind can only interact with cars ahead of it. Once a slower fleet forms, any faster car behind it will eventually slow down and join it. By scanning from right to left (closest to farthest), you only need to compare arrival times, which avoids simulating movement.
Approach 2: Monotonic Stack of Arrival Times (O(n log n) time, O(n) space)
This variation uses the same sorting step but explicitly models fleets using a stack. After sorting cars by position descending, compute the arrival time for each car and push it onto a stack. If the new time is less than or equal to the time on top of the stack, it means the car catches the fleet ahead, so you discard it instead of creating a new entry. The stack therefore stays monotonic increasing in arrival time, which is a classic monotonic stack pattern.
The number of elements left in the stack equals the number of fleets. Conceptually, each stack entry represents the final arrival time of a fleet that cannot be caught by any car behind it.
Recommended for interviews: The sorting + time comparison approach is what most interviewers expect. It shows you can reduce a simulation problem to a mathematical observation about arrival times. Mentioning the monotonic stack interpretation demonstrates deeper understanding, especially when discussing patterns involving arrays and ordered traversal.
To solve the Car Fleet problem, we can calculate the time it takes for each car to reach the target. By sorting cars based on their starting positions and calculating their respective arrival times, we can determine when fleets are formed. Cars that catch up to a fleet at the target will become part of that fleet.
This solution uses a struct to store the position and time of each car to reach the target. By sorting cars based on position in descending order, we process them starting from the farthest from the target. We keep track of the `currentTime` indicating the time of the last fleet formed. If a car's time is greater than this, it starts a new fleet, and we update `currentTime` to this car's time.
Time Complexity: O(n log n) due to sorting of cars
Space Complexity: O(n) for storing car times and positions
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Time Calculation | Time Complexity: O(n log n) due to sorting of cars |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Time Comparison | O(n log n) | O(1) | Best general solution. Minimal memory and straightforward logic. |
| Monotonic Stack of Arrival Times | O(n log n) | O(n) | Useful when explaining fleet formation using stack or monotonic patterns. |
Car Fleet - Leetcode 853 - Python • NeetCode • 321,678 views views
Watch 9 more video solutions →Practice Car Fleet with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor