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 ith 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:

1. 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 the lambda function as the key for the sorted function to sort the indices based on their associated values in the position array. The resulting idx 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])

2. Initialize Variables: Two variables are used, ans to count the number of car fleets, and pre to store the time taken by the previously processed car (or fleet) to reach the destination.

   1ans = pre = 0

3. 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]:

4. 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]).

5. 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 count ans by 1.

   1if t > pre:
   2    ans += 1
   3    pre = t

   The current time t is now the new pre because it will serve as the comparison time for the next car in the iteration.

6. 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

Example 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:

1. 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

2. Initialize Variables: ans = 0, pre = 0

3. 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 have ans = 1 and pre = 12.

   For i = 3 (Car 4):

   • t = (12 - 5) / 3 ≈ 2.33
   • Since t < pre, we do not increment ans, and pre remains 12.

   For i = 1 (Car 2):

   • t = (12 - 8) / 4 = 1
   • Since t < pre, we do not increment ans, and pre remains 12.

   For i = 0 (Car 1):

   • t = (12 - 10) / 2 = 1
   • Since t < pre, we do not increment ans, and pre remains 12.

4. 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

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 of O(N log N), where N 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 size O(N).
• Variables ans and pre 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.