Car Fleet - Leetcode 853 - Python
Car Fleet - Video Solution
Watch 10 video solutions for Car Fleet, a medium level problem involving Array, Stack, Sorting. This walkthrough by NeetCode has 345,684 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at
target. - The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
- The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches
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:
- The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
- Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches
target.
Constraints:
n == position.length == speed.length1 <= n <= 1050 < target <= 1060 <= position[i] < target- All the values of
positionare unique. 0 < speed[i] <= 106
Approach Overview
Problem 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.
Complexity Analysis
| 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. |