Car Fleet
Problem
Given a target position and two arrays position and speed representing cars on a one-lane road, return the number of car fleets that will arrive at the target, where a car fleet is a group of cars traveling at the same speed and position such that no car in the fleet can pass another.
- 1 ≤ position.length == speed.length ≤ 10⁴
- 0 < target ≤ 10⁶
- 0 ≤ position[i] < target
- 1 ≤ speed[i] ≤ 10⁶
- All positions are unique
Example
target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]3Sort cars by starting position descending: [(10,2), (8,4), (5,1), (3,3), (0,1)]. Calculate time to reach target: [1, 1, 7, 3, 12]. Starting from the car closest to the target (position 10), it takes 1 hour to arrive. The car at position 8 also takes 1 hour, so it forms a fleet with the car at 10. The car at position 5 takes 7 hours, which is longer, so it forms a new fleet. The car at position 3 takes 3 hours, which is less than 7, so it catches up and merges with the car at 5, forming one fleet. The car at position 0 takes 12 hours, forming the last fleet. Total fleets: 3.
Approach
Straightforward Solution
A brute-force approach would simulate the movement of each car over time, checking for collisions or merges, which is computationally expensive and inefficient for large inputs.
Core Observation
Cars closer to the target with longer or equal arrival times form fleets with cars behind them that catch up. The key is to process cars in descending order of position and compare their arrival times to the target to determine fleet formation.
Path to Optimal
PreviewSorting cars by their starting positions in descending order allows processing from the closest to the target backward…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewSort cars by position descending. Iterate through each car, compute its time to reach the target, and maintain a stack of fleet arrival times…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log n)
Sorting the cars by position takes O(n log n). The single pass through the sorted list with stack operations is O(n), resulting in overall O(n log n) time.
Space
O(n)
The stack can hold up to n fleet times in the worst case, requiring O(n) auxiliary space.
Pattern Spotlight
Greedy Algorithms (Monotonic Stack for Grouping)
When grouping elements based on a monotonic property (like arrival times), process in order and use a stack to maintain the boundary conditions of groups, merging elements that do not exceed the current group's threshold.
Solution
| 1 | class Solution:
|
| 2 | def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
|
| 3 | cars = sorted(zip(position, speed), reverse=True)
|
| 4 | time_stack = []
|
| 5 |
|
| 6 | for p, s in cars:
|
| 7 | time_to_arrive = (target - p) / s
|
| 8 |
|
| 9 | if not time_stack or time_to_arrive > time_stack[-1]:
|
| 10 | time_stack.append(time_to_arrive)
|
| 11 |
|
| 12 | return len(time_stack) |
Step-by-Step Solution
Sort Cars by Position Descending to Process from Target Backwards
| 3 | cars = sorted(zip(position, speed), reverse=True)
|
Objective
To order cars so that processing starts from the car closest to the target, enabling correct fleet grouping.
Key Insight
Sorting by position descending aligns cars in the order they would be encountered traveling towards the target. This ordering is crucial because a car can only catch up to cars ahead of it, never those behind. By processing from the closest car backward, the algorithm can efficiently determine fleet formation by comparing arrival times.
Interview Quick-Check
Core Logic
Sorting cars by position descending ensures that each car is compared only to cars ahead, reflecting the physical constraints of the problem.
Common Pitfalls & Bugs
Sorting in ascending order or not sorting at all would prevent correct fleet detection because cars behind might be processed before those ahead.
Calculate Each Car's Time to Reach Target and Group into Fleets Using a Stack
To compute arrival times and use a stack to merge cars into fleets based on their relative arrival times.
Return the Number of Fleets as the Size of the Stack
To provide the final count of distinct car fleets formed by returning the stack size.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if not time_stack or time_to_arrive > time_stack[-1]:Check if the stack is empty or if the current car's arrival time is greater than the last fleet's time.
This condition identifies whether the current car cannot catch up to the fleet ahead and thus forms a new fleet, which is the key greedy decision enabling correct fleet grouping.
cars = sorted(zip(position, speed), reverse=True)Sort cars by their starting position in descending order, pairing position and speed.
Sorting cars from closest to farthest from the target allows processing in the order cars would be encountered traveling towards the target, which is essential for correctly grouping fleets.
Full line-by-line criticality + rationale for all 7 lines available on Pro.
Test Your Understanding
Why does processing cars in descending order of position and comparing arrival times correctly identify fleets without simulating their movement?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Car Fleet from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Car Fleet drill