Car Fleet LeetCode Problem 853 [Python Solution]

Let’s rev up our engines and embark on a journey to conquer the intriguing Car Fleet LeetCode problem, in the spirit of efficient problem-solving.

Problem Overview

Question

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 array 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 have 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 a one car fleet.

Return the number of car fleets that will arrive at the destination.

…

In this problem, we are given n cars traveling along a one-lane road toward a common destination. Each car has a specific position and speed.

However, cars cannot overtake each other but can form a car fleet when they reach the same position and travel at the same speed.

Our task is to determine how many car fleets will arrive at the destination.

Example 1:

Input: 
- Target: 12
- Positions: [10, 8, 0, 5, 3]
- Speeds: [2, 4, 1, 1, 3]

Output: 3

Explanation: 
- The cars starting at positions 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
- The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
- The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches the target.

Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.

Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Understanding the Constraints

Before diving into the solution, let’s understand the problem constraints:

n is the number of cars, where 1 <= n <= 105.
The target position is greater than 0 and less than or equal to 106.
Car positions are unique and range from 0 to the target position.
Car speeds are greater than 0 and less than or equal to 106.

Car Fleet LeetCode Problem Solution

To solve this problem efficiently, we will use a stack-based approach.

We will iterate through the cars in reverse order, starting with the car closest to the destination.

This approach allows us to determine if a car collides with the car ahead of it.

Here is the Python solution:

View on GitHub ➹

def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    # Create pairs of position and speed
    pair = [(p, s) for p, s in zip(position, speed)]
    # Sort pairs in reverse order based on position
    pair.sort(reverse=True)
    stack = []  # Stack to track arrival times
    
    for p, s in pair:  # Iterate in reverse sorted order
        time_to_destination = (target - p) / s  # Calculate time to reach destination
        if not stack or time_to_destination > stack[-1]:
            # If the stack is empty or this car does not collide with the car ahead, add it to the stack
            stack.append(time_to_destination)
    
    return len(stack)  # The length of the stack represents the number of car fleets

Time and Space Complexity

The time complexity of this solution is O(n log n) due to the sorting of the cars based on their positions.

The space complexity is O(n) as we store the cars in an array and maintain a stack of arrival times.

Reasoning Behind Our Approach

We start by visualizing the problem as a set of linear equations, with time on one axis and position on another.

Cars are represented as lines on this graph, and we determine car fleets by identifying points where these lines intersect before reaching the destination.

Our algorithm iterates through the cars in reverse order, ensuring that we consider the car closest to the destination first.

For each car, we calculate the time it takes to reach the destination and compare it with the car ahead in the stack.

If they collide (i.e., the time is less than or equal to the time of the car ahead), we remove the car from the stack.

Otherwise, we add it to the stack.

This approach efficiently handles the problem constraints and allows us to find the number of car fleets that will arrive at the destination.

Conclusion

In this blog post, we explored the Car Fleet LeetCode problem, where we had to determine the number of car fleets that would arrive at a common destination.

We approached the problem by visualizing it as a set of linear equations and using a stack-based algorithm to efficiently find the answer.

The algorithm sorts the cars by their positions in reverse order and calculates the arrival times to determine car fleets.

With a time complexity of O(n log n), this solution efficiently handles large inputs and provides a clear understanding of how car fleets are formed on a one-lane road.

We hope this explanation has helped you understand the problem and the solution.

If you have any questions, suggestions, or comments, please feel free to share them below. Happy coding!