{x}
blog image

Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

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

 

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Explanation:

  • The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
  • The car starting at 0 (speed 1) 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 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 car starting at 4 (speed 1) travels to 5.
  • Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

 

Constraints:

  • n == position.length == speed.length
  • 1 <= n <= 105
  • 0 < target <= 106
  • 0 <= position[i] < target
  • All the values of position are unique.
  • 0 < speed[i] <= 106

Solution Explanation for LeetCode 853: Car Fleet

This problem involves determining the number of car fleets that will reach the destination. A car fleet is a group of cars traveling together at the same speed (the speed of the slowest car in the fleet).

Approach:

The key insight is that we only need to consider cars in reverse order of their positions. A faster car behind a slower car will eventually catch up. Therefore, we can process the cars from the furthest to the closest to the target.

We sort the cars by their positions in descending order. For each car, we calculate the time it takes to reach the target. If this time is greater than the time of the previous car (the car ahead of the current car in terms of position), it means this car forms a new fleet. Otherwise, it merges with the existing fleet.

Algorithm:

  1. Sort: Sort the cars based on their positions in descending order (farthest first). We use the indices to track the original positions in the arrays.

  2. Iterate and Calculate Time: Iterate through the sorted cars. For each car, calculate the time t it takes to reach the target: t = (target - position[i]) / speed[i].

  3. Fleet Formation: Maintain a variable pre to track the maximum time among previously processed cars. If the current car's time t is greater than pre, it means this car will not catch up with any existing fleet, forming a new fleet. Increment the fleet count ans and update pre with t. Otherwise, this car joins the existing fleet.

Time Complexity Analysis:

  • Sorting the cars takes O(N log N) time, where N is the number of cars.
  • Iterating through the sorted cars takes O(N) time.
  • Therefore, the overall time complexity is dominated by the sorting step, resulting in O(N log N).

Space Complexity Analysis:

  • We use an array of indices to track the original positions which takes O(N) space.
  • The space used for other variables is constant.
  • Thus, the overall space complexity is O(N).

Code Implementation (Python):

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(range(len(position)), key=lambda i: position[i], reverse=True)  #Sort by position descending, get indices
        ans = 0
        max_time = 0  #Initialize max time to 0
 
        for i in cars:
            time_to_reach_target = (target - position[i]) / speed[i]
            if time_to_reach_target > max_time:
                ans += 1
                max_time = time_to_reach_target
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithmic steps, with minor syntax differences specific to each language. The time and space complexity remain the same across all implementations.