Car Fleet medium

Problem Statement

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array position of integers representing the initial positions of the n cars, and an array speed representing the speeds of the cars. A car can only pass another car if it is faster.

Determine the number of car fleets that will form. A car fleet is a group of cars that are traveling at the same speed and will eventually reach the same destination.

Example 1

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

Output: 3

Explanation:

• Car 1 at position 10 with speed 2 will reach the target in (12-10)/2 = 1 hour.
• Car 2 at position 8 with speed 4 will reach the target in (12-8)/4 = 1 hour.
• Car 3 at position 0 with speed 1 will reach the target in (12-0)/1 = 12 hours.
• Car 4 at position 5 with speed 1 will reach the target in (12-5)/1 = 7 hours.
• Car 5 at position 3 with speed 3 will reach the target in (12-3)/3 = 3 hours.

The cars will reach the target at times [1, 1, 12, 7, 3] hours. Sorting these times, we get [1, 1, 3, 7, 12]. We can see that cars 1 and 2 will form a fleet because they arrive at the same time, car 5 forms its own fleet, car 4 forms its own fleet, and car 3 forms its own fleet. Therefore, there are 3 car fleets.

Example 2

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation:

Only one car, so only one fleet.

Steps

1. Calculate arrival times: For each car, calculate the time it takes to reach the target using (target - position) / speed.
2. Sort by arrival time: Sort the cars in ascending order based on their arrival times.
3. Count fleets: Iterate through the sorted cars. If a car's arrival time is greater than the previous car's arrival time, it forms a new fleet. Otherwise, it joins the existing fleet.

Explanation

The key idea is that if a slower car is ahead of a faster car, the faster car will catch up to the slower car before reaching the target. Therefore, we only need to consider the arrival times of the cars. By sorting the cars by arrival time, we can easily identify groups of cars that will arrive at the same time, forming fleets.

Code

def carFleet(target, position, speed):
    """
    Calculates the number of car fleets.

    Args:
        target: The target position.
        position: A list of car positions.
        speed: A list of car speeds.

    Returns:
        The number of car fleets.
    """

    n = len(position)
    if n == 0:
        return 0

    # Pair positions and speeds, then sort by position in descending order.
    cars = sorted(zip(position, speed), reverse=True)  

    arrival_times = []
    for pos, spd in cars:
        arrival_times.append((target - pos) / spd)

    fleets = 1  # Initialize with at least one fleet
    max_arrival = arrival_times[0]  #Keep track of the latest arrival time

    for i in range(1, len(arrival_times)):
        if arrival_times[i] > max_arrival:  #If current arrival time is greater than previous one, it's a new fleet
            fleets += 1
            max_arrival = arrival_times[i]

    return fleets

Complexity

• Time Complexity: O(n log n), dominated by the sorting step.
• Space Complexity: O(n), to store the arrival times.