853. Car Fleet
Problem Description
The problem presents a scenario where n
cars are traveling towards a destination at different speeds and starting from different positions on a single-lane road. The destination is target
miles away. We are provided with two arrays of integers: position
and speed
. Each index i
in the arrays corresponds to the i
th car, with position[i]
representing the initial position of the car and speed[i]
being its speed in miles per hour.
The key condition is that cars cannot overtake each other. When a faster car catches up to a slower one, it will slow down to form a "car fleet" and they will move together at the slower car's speed. This also applies to multiple cars forming a single fleet if they meet at the same point.
Our task is to determine the number of car fleets that will eventually arrive at the destination. A car fleet can consist of just one car, or multiple cars if they have caught up with each other along the way. Even if a car or fleet catches up with another fleet at the destination point, they are counted as one fleet.
Intuition
To solve this problem, an intuitive approach is to figure out how long it would take for each car to reach the destination independently and then see which cars would form fleets along the way. By sorting the cars based on their starting positions, we can iterate from the one closest to the destination to the one furthest from it. This allows us to determine which cars will catch up to each other.
As we iterate backwards, we calculate the time t
it takes for each car to reach the destination:
t = (target - position[i]) / speed[i]
We compare this time with the time of the previously considered car (starting from the closest to the target). If t
is greater than the pre
(previous car's time), this means that the current car will not catch up to the car(s) ahead (or has formed a new fleet) before reaching the destination, and thus we increment our fleet count ans
. The current car's time then becomes the new pre
.
This process is repeated until we have considered all cars. The total number of fleets (ans
) is the answer we are looking for. This method ensures that we count all fleets correctly, regardless of how many cars they start with or how many they pick up along the way.
Learn more about Stack, Sorting and Monotonic Stack patterns.
Solution Approach
The solution is implemented in Python and is composed of the following steps:
-
Sort Car Indices by Position: A list of indices is created from 0 to
n-1
, which is then sorted according to the starting positions of the cars. This sorting step uses thelambda
function as the key for thesorted
function to sort the indices based on their associated values in theposition
array. The resultingidx
list will help us traverse the cars in order of their starting positions from closest to furthest relative to the destination.1idx = sorted(range(len(position)), key=lambda i: position[i])
-
Initialize Variables: Two variables are used,
ans
to count the number of car fleets, andpre
to store the time taken by the previously processed car (or fleet) to reach the destination.1ans = pre = 0
-
Reverse Iterate through Sorted Indices: By iterating over the sorted indices in reverse order, the algorithm evaluates each car starting with the one closest to the destination.
1for i in idx[::-1]:
-
Calculate Time to Reach Destination: For each car, the time
t
to reach the destination is calculated using the formula:1t = (target - position[i]) / speed[i]
This formula calculates the time by taking the distance to the destination (
target - position[i]
) and dividing it by the car's speed (speed[i]
). -
Evaluate Fleets: If the calculated time
t
is greater than the time of the last car (or fleet)pre
, it implies that the current car will not catch up to any car ahead of it before reaching the destination. Hence, we have found a new fleet, and we increment the fleet countans
by 1.1if t > pre: 2 ans += 1 3 pre = t
The current time
t
is now the newpre
because it will serve as the comparison time for the next car in the iteration. -
Return Fleet Count: After all the iterations, the variable
ans
holds the total number of car fleets, and its value is returned.
The primary data structure used here is a list for indexing the cars. The sorting pattern is essential to correctly pair cars that will become fleets, and the reverse iteration allows the algorithm to efficiently compare only the necessary cars. The time complexity of the algorithm is dominated by the sorting step, making the overall time complexity O(n log n)
due to the sort, and the space complexity is O(n)
for storing the sorted indices.
1return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach to a small example to better understand how it works.
Imagine we have 4 cars with positions and speeds given by the following arrays:
position
: [10, 8, 0, 5]speed
: [2, 4, 1, 3]target
: 12 miles away
First, letās visualize the initial state of the cars and the target:
1Target (12 miles) 2| 3| Car 1 (10 miles, 2 mph) 4| 5| Car 2 (8 miles, 4 mph) 6| 7| Car 4 (5 miles, 3 mph) 8| 9| Car 3 (0 miles, 1 mph) 10| 11Start
Following the solution approach:
- Sort Car Indices by Position: After sorting the indices by the starting positions in descending order, we have the new order of car indexes as
idx = [0, 1, 3, 2]
. Now the cars are sorted by proximity to the destination:
1Target (12 miles) 2| 3| Car 1 (idx = 0) 4| 5| Car 2 (idx = 1) 6| 7| Car 4 (idx = 3) 8| 9| Car 3 (idx = 2) 10| 11Start
-
Initialize Variables:
ans = 0
,pre = 0
-
Reverse Iterate through Sorted Indices: We iterate in reverse through
idx
as[2, 3, 1, 0]
.For
i = 2
(Car 3):t = (12 - 0) / 1 = 12
- Since
t > pre
, we haveans = 1
andpre = 12
.
For
i = 3
(Car 4):t = (12 - 5) / 3 ā 2.33
- Since
t < pre
, we do not incrementans
, andpre
remains12
.
For
i = 1
(Car 2):t = (12 - 8) / 4 = 1
- Since
t < pre
, we do not incrementans
, andpre
remains12
.
For
i = 0
(Car 1):t = (12 - 10) / 2 = 1
- Since
t < pre
, we do not incrementans
, andpre
remains12
.
-
Return Fleet Count: We have
ans = 1
, indicating that all the cars will form one fleet by the time they reach the destination.
In summary, even though the cars started at different positions and had different speeds, they caught up with each other on the way to the target. Hence, there will be 1 car fleet by the time they reach the destination.
Solution Implementation
1from typing import List
2
3class Solution:
4 def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
5 # Pair each car's position with its index and sort the pairs in ascending order of positions
6 car_indices_sorted_by_position = sorted(range(len(position)), key=lambda idx: position[idx])
7
8 # Initialize the count of car fleets and the time of the previously counted fleet
9 fleet_count = 0
10 previous_time = 0
11
12 # Iterate over the cars from the one closest to the target to the furthest
13 for i in car_indices_sorted_by_position[::-1]: # Reverse iteration
14 # Calculate the time needed for the current car to reach the target
15 time_to_reach_target = (target - position[i]) / speed[i]
16 # If this time is greater than the time of the previously counted fleet,
17 # it means this car cannot catch up with that fleet and forms a new fleet.
18 if time_to_reach_target > previous_time:
19 fleet_count += 1 # Increment fleet count
20 previous_time = time_to_reach_target # Update the time of the last fleet
21
22 # Return the total number of fleets
23 return fleet_count
24
1class Solution {
2
3 // Function to count the number of car fleets that will arrive at the target
4 public int carFleet(int target, int[] positions, int[] speeds) {
5 // Number of cars
6 int carCount = positions.length;
7 // Array to hold the indices of the cars
8 Integer[] indices = new Integer[carCount];
9
10 // Populate the indices array with the array indices
11 for (int i = 0; i < carCount; ++i) {
12 indices[i] = i;
13 }
14
15 // Sort the indices based on the positions of the cars in descending order
16 Arrays.sort(indices, (a, b) -> positions[b] - positions[a]);
17
18 // Count of car fleets
19 int fleetCount = 0;
20 // The time taken by the previous car to reach the target
21 double previousTime = 0;
22
23 // Iterate through the sorted indices array
24 for (int index : indices) {
25 // Calculate the time taken for the current car to reach the target
26 double timeToReach = 1.0 * (target - positions[index]) / speeds[index];
27
28 // If the time taken is greater than the previous time, it forms a new fleet
29 if (timeToReach > previousTime) {
30 fleetCount++;
31 previousTime = timeToReach; // Update the previous time
32 }
33 // If the time is less or equal, it joins the fleet of the previous car
34 }
35 // Return the total number of fleets
36 return fleetCount;
37 }
38}
39
1#include <algorithm> // For sort and iota functions
2#include <vector> // For using vectors
3
4class Solution {
5public:
6 int carFleet(int target, vector<int>& positions, vector<int>& speeds) {
7 int numCars = positions.size(); // Number of cars
8 vector<int> indices(numCars); // Initialize a vector to store indices
9 iota(indices.begin(), indices.end(), 0); // Filling the indices vector with 0, 1, ..., numCars - 1
10
11 // Sort cars by their position in descending order, so the farthest is first
12 sort(indices.begin(), indices.end(), [&](int i, int j) {
13 return positions[i] > positions[j];
14 });
15
16 int fleetCount = 0; // Initializing count of car fleets
17 double lastFleetTime = 0; // Time taken by the last fleet to reach the target
18
19 // Iterate over the sorted cars by their initial position
20 for (int idx : indices) {
21 double timeToTarget = 1.0 * (target - positions[idx]) / speeds[idx]; // Calculate the time to target
22
23 // If the current car's time to target is greater than the last fleet's time,
24 // it becomes a new fleet as it cannot catch up to the one in front
25 if (timeToTarget > lastFleetTime) {
26 fleetCount++; // Increment the number of fleets
27 lastFleetTime = timeToTarget; // And update the last fleet's time to this car's time
28 }
29 }
30
31 return fleetCount; // Return total number of fleets
32 }
33};
34
1function carFleet(targetDistance: number, positions: number[], speeds: number[]): number {
2 const numCars = positions.length; // Number of cars.
3 // Create an array of indices corresponding to cars, sorted in descending order of their starting positions.
4 const sortedIndices = Array.from({ length: numCars }, (_, index) => index)
5 .sort((indexA, indexB) => positions[indexB] - positions[indexA]);
6
7 let fleetCount = 0; // Counter for the number of car fleets.
8 let previousTimeToTarget = 0; // Time taken for the previous car (or fleet) to reach the target.
9
10 // Loop through the sorted car indices.
11 for (const index of sortedIndices) {
12 // Calculate time required for the current car to reach the target.
13 const currentTimeToTarget = (targetDistance - positions[index]) / speeds[index];
14
15 // If the current car takes longer to reach the target than the previous car (or fleet),
16 // it cannot catch up and forms a new fleet.
17 if (currentTimeToTarget > previousTimeToTarget) {
18 fleetCount++; // Increment the fleet counter.
19 previousTimeToTarget = currentTimeToTarget; // Update the time to match the new fleet's time.
20 }
21 }
22
23 return fleetCount; // Return the total number of car fleets.
24}
25
Time and Space Complexity
The given Python code is to calculate the number of car fleets that will reach the target destination without any fleet getting caught up by another. The time complexity and space complexity of the code are analyzed below.
Time Complexity
The time complexity of the code can be analyzed as follows:
- Sorting the list of positions: This is done by using the
.sort()
method, which typically has a time complexity ofO(N log N)
, whereN
is the length of the positions list. - The for loop iterates over the list of positions in reverse: This has a time complexity of
O(N)
as it goes through each car once. - Therefore, the overall time complexity of the function is dominated by the sorting operation and is
O(N log N)
.
Space Complexity
The space complexity of the code can be analyzed as follows:
- Additional space is required for the sorted indices array
idx
, which will be of sizeO(N)
. - Variables
ans
andpre
use constant space:O(1)
. - Space taken by sorting depends on the implementation, but for most sorting algorithms such as Timsort (used in Python's sort method), it requires
O(N)
space in the worst case. - Therefore, the overall space complexity of the function is
O(N)
.
Combining the time and space complexities, we get the following results:
- Time Complexity:
O(N log N)
- Space Complexity:
O(N)
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or