Car Fleet
Understanding the Problem
Cars start at different positions on a single-lane road, all heading toward the same destination. A faster car behind a slower one eventually catches up, and since there is no passing, it slows down to match the slower car's speed. From that point the two travel together as a fleet. The question is how many separate fleets arrive at the destination.
Nothing about the motion needs to be simulated. Calculate how long each car would take to reach the destination if it drove alone: (target - position) / speed. A car behind reaches the destination at or before the car ahead exactly when its solo arrival time is less than or equal to the other's. Since it cannot pass, that means it catches up at or before the target and merges into the fleet ahead, adopting the slower arrival time. If its solo time is longer, it never catches up and forms a separate fleet.
Key Constraints:
1 <= n <= 10^5→ With up to 100,000 cars, we need O(n log n) or better. An O(n^2) approach checking all pairs of cars won't work.0 <= position[i] < target→ All positions are strictly less than the target, so every car still has distance to cover and every arrival time is positive.- All positions are unique → No two cars start at the same place, so sorting by position produces no ties.
Approach 1: Brute Force (Simulation)
Intuition
Simulate the merging directly. Sort the cars by position, compute each car's solo arrival time, and scan adjacent pairs: whenever a car behind would arrive at or before the car ahead of it, it catches up and merges into that car's fleet. A merge can expose a new adjacent pair (the car behind the merged one now sits directly behind the fleet leader), so the scan repeats until a full pass produces no merges. The cars that survive are the fleet leaders, one per fleet.
Algorithm
- Create an array of (position, speed) pairs and sort by position in descending order (closest to target first).
- Calculate the time to reach the target for each car:
time[i] = (target - position[i]) / speed[i]. - Scan the active cars from front to back. Whenever an active car's arrival time is less than or equal to the time of the active car ahead of it, mark it merged and drop it from later passes. Its fleet now arrives at the leader's time, which is what later comparisons use.
- Repeat full passes until one completes with no merges.
- Count the cars still active. Each one leads a fleet.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). Sorting takes O(n log n), but the iterative merging can take up to O(n) passes, each scanning O(n) cars. In the worst case, each pass merges only one car, leading to O(n) passes of O(n) scans each.
- Space Complexity: O(n). We store the indices array and arrival times array, both of size n.
The repeated passes are what make this slow. Merging only flows in one direction, from a car into the fleet ahead of it, so a single front-to-back pass that tracks the current fleet's arrival time settles every car without revisiting anything.
Approach 2: Sort and Single Pass (Optimal)
Intuition
For each car, calculate how long it would take to reach the target if driving unobstructed: time = (target - position) / speed. Sort the cars by position from closest to the target to farthest and process them in that order.
The car closest to the target has nothing ahead of it, so it leads the first fleet. For every later car, compare its solo arrival time against the arrival time of the fleet directly ahead. If its time is less than or equal, it catches up and merges into that fleet. If its time is greater, it never catches up and starts a new fleet.
A fleet's arrival time never changes after its lead car is processed: the leader is the slowest member, and every car that joins is faster and falls in behind it. So one running maximum of arrival times is enough state for the whole scan. Each time a car's time exceeds the current maximum, that car starts a new fleet and the maximum updates.
A car can only be blocked by the fleet directly ahead of it, and a fleet's arrival time equals the solo time of its lead car. Scanning from the target backward, the running maximum therefore always holds the arrival time of the fleet directly ahead of the current car. A car with a smaller or equal time reaches the target no later than that fleet, so it must catch it at or before the target and merges, leaving the maximum unchanged. A car with a larger time can never catch that fleet, regardless of what happens behind it, so it leads a new fleet and becomes the new maximum.
Algorithm
- Pair each car's position with its speed. Sort by position in descending order (closest to target first).
- For each car, calculate
time = (target - position) / speed. - Initialize a fleet counter and a running maximum arrival time, both to 0. Every arrival time is positive because
position < target, so the first car always registers as a new fleet. - Iterate through the sorted cars:
- If this car's arrival time is strictly greater than the running maximum, it forms a new fleet. Increment the counter and update the maximum.
- Otherwise, it merges into the fleet ahead.
- Return the counter.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n). Sorting the cars by position takes O(n log n). The single pass through the sorted array is O(n). The sort dominates.
- Space Complexity: O(n). We create the pairs array of size n.
Approach 2 is already optimal in time complexity. We can make the monotonic stack pattern more explicit by using an actual stack data structure instead of a running maximum.
Approach 3: Stack-Based Solution (Explicit Stack Variant)
Intuition
This is the same algorithm as Approach 2 with an explicit stack in place of the running maximum. Process cars from closest to the target to farthest and push an arrival time only when it is strictly greater than the stack top. Each pushed time is one fleet's arrival time, so the final stack size is the answer.
The stack holds a strictly increasing sequence of arrival times, one per fleet, which is the monotonic stack pattern in its simplest form. It also preserves every fleet's arrival time, which matters when the individual times are needed and not only the count. When the count alone is the goal, the running maximum from Approach 2 does the same work with one variable.
Algorithm
- Sort cars by position descending.
- Calculate arrival times.
- Initialize an empty stack.
- For each car's arrival time:
- If the stack is empty or the time is strictly greater than the stack top, push it.
- Otherwise, skip it (car merges into the fleet at the top of the stack).
- Return the stack size.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n). Same as Approach 2. Sorting dominates at O(n log n), and the stack pass is O(n).
- Space Complexity: O(n). The pairs array is O(n), and the stack can hold up to n elements in the worst case (when every car forms its own fleet).