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
Sorting cars by their starting positions in descending order allows processing from the closest to the target backward. Calculating each car's time to reach the target and comparing it with the last recorded fleet time enables grouping cars into fleets without explicit simulation. If a car's arrival time is less than or equal to the fleet time ahead, it merges into that fleet; otherwise, it starts a new fleet.
Optimal Approach
Sort cars by position descending. Iterate through each car, compute its time to reach the target, and maintain a stack of fleet arrival times. If the current car's time is greater than the top of the stack, it forms a new fleet and is pushed onto the stack. Otherwise, it merges with the fleet ahead. The number of fleets equals the size of the stack at the end.
Time
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) |
| 1 | class Solution { |
| 2 | public int carFleet(int target, int[] position, int[] speed) { |
| 3 | int n = position.length; |
| 4 | int[][] cars = new int[n][2]; |
| 5 | for (int i = 0; i < n; i++) { |
| 6 | cars[i][0] = position[i]; |
| 7 | cars[i][1] = speed[i]; |
| 8 | } |
| 9 | Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0])); |
| 10 | List<Double> timeStack = new ArrayList<>(); |
| 11 | |
| 12 | for (int[] car : cars) { |
| 13 | double timeToArrive = (double) (target - car[0]) / car[1]; |
| 14 | |
| 15 | if (timeStack.isEmpty() || timeToArrive > timeStack.get(timeStack.size() - 1)) { |
| 16 | timeStack.add(timeToArrive); |
| 17 | } |
| 18 | } |
| 19 | |
| 20 | return timeStack.size(); |
| 21 | } |
| 22 | } |
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
| 4 | time_stack = []
|
| 6 | for p, s in cars:
|
| 7 | time_to_arrive = (target - p) / s
|
| 9 | if not time_stack or time_to_arrive > time_stack[-1]:
|
| 10 | time_stack.append(time_to_arrive)
|
Objective
To compute arrival times and use a stack to merge cars into fleets based on their relative arrival times.
Key Insight
The time for each car to reach the target is (target - position) / speed. By iterating through cars in descending position order, the algorithm compares each car's arrival time to the last fleet's arrival time on the stack. If the current car arrives later, it forms a new fleet; if earlier or equal, it merges into the existing fleet. The stack maintains a monotonic decreasing sequence of arrival times representing distinct fleets.
Interview Quick-Check
Core Logic
Using a stack to track fleet arrival times allows efficient grouping: a car merges into the fleet ahead if its arrival time is less than or equal to the fleet's time.
State & Boundaries
The condition to push a new fleet time onto the stack is that the current car's arrival time is strictly greater than the top of the stack.
Common Pitfalls & Bugs
Failing to compare arrival times correctly or mishandling the stack can lead to incorrect fleet counts.
Return the Number of Fleets as the Size of the Stack
| 12 | return len(time_stack) |
Objective
To provide the final count of distinct car fleets formed by returning the stack size.
Key Insight
Each element in the stack represents a unique fleet's arrival time. Since the stack only grows when a new fleet is formed, its size directly corresponds to the total number of fleets arriving at the target.
Interview Quick-Check
Core Logic
The stack size after processing all cars equals the number of distinct fleets.
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.
time_to_arrive = (target - p) / sCalculate the time for the current car to reach the target.
Computing arrival time is critical to determine if the car will form a new fleet or merge with an existing one based on relative speeds and positions.
time_stack.append(time_to_arrive)Append the current car's arrival time to the stack, representing a new fleet.
Adding a new fleet time to the stack preserves the monotonic decreasing order of arrival times, ensuring that subsequent cars can be correctly merged or separated.
time_stack = []Initialize an empty stack to store fleet arrival times.
The stack will maintain a monotonic sequence of fleet arrival times, enabling efficient grouping of cars into fleets without explicit simulation.
for p, s in cars:Iterate over each car's position and speed in descending order of position.
Processing cars from closest to farthest ensures that each car is compared only to fleets ahead, reflecting the physical constraints of the problem.
return len(time_stack)Return the total number of fleets as the size of the stack.
The stack size directly corresponds to the number of distinct fleets formed, as each fleet is represented by a unique arrival time on the stack.
Test Your Understanding
Why does processing cars in descending order of position and comparing arrival times correctly identify fleets without simulating their movement?
Because cars closer to the target with longer or equal arrival times act as fleet leaders, and any car behind with a shorter or equal arrival time will catch up and merge into that fleet. Processing in descending order ensures that each car is compared only to the fleet ahead, enabling correct grouping without explicit simulation.
Related Problems
Greedy 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