Car Fleet
Explanation & Solution
Description
There are n cars going to the same destination along a one-lane road. The destination is target miles away.
You are given two integer arrays position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to be at the same position).
A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
Return the number of car fleets that will arrive at the destination.
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
- Cars at 10 (speed 2) and 8 (speed 4) become a fleet at 12. Fleet 1.
- Car at 0 (speed 1) won't catch any. Fleet 2.
- Cars at 5 (speed 1) and 3 (speed 3) become a fleet at 6. Fleet 3.
Constraints
n == position.length == speed.length1 <= n <= 10^50 < target <= 10^60 <= position[i] < target0 < speed[i] <= 10^6
Approach
Stacks pattern
1. Calculate Arrival Times
- For each car, compute
time = (target - position) / speed - This is the time it would take if it drove alone without being blocked
2. Sort by Position (Descending)
- Sort cars by position from closest to target to farthest
- This lets us process cars in the order they would be encountered on the road
3. Stack-Based Fleet Counting
- For each car (from closest to farthest):
- If its arrival time is greater than the stack's top → it's a new fleet (it's slower, can't catch the car ahead)
- If its arrival time is ≤ the stack's top → it merges into the fleet ahead (it catches up)
- Push only when creating a new fleet
4. Result
- The stack size is the number of distinct fleets
Key Insight
- A car behind with a shorter or equal arrival time will always catch up to or match the car ahead
- A car behind with a longer arrival time can never catch up — it forms a new fleet
- Sorting by position lets us compare each car against the fleet directly ahead of it
- Time: O(n log n) for sorting, Space: O(n)