Car Fleet medium

Problem Statement

You are given an array target representing the positions of several cars on a road, and an array speed representing the speed of each car. All cars are moving towards the same destination at the end of the road (position 0). A car can only pass another car if its speed is strictly greater than the other car's speed. If two cars have the same speed, they will remain at the same relative position.

Determine the number of car fleets that will form. A car fleet is defined as a group of cars that will arrive at the same time at the end of the road.

Example 1

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

Output: 2

Explanation:

• The cars at positions 10 and 8 will arrive at the same time.
• The cars at positions 5 and 3 will arrive at the same time.
• The car at position 0 is already at the destination.

Therefore, there are 2 car fleets.

Example 2

Input: target = [3,2,1,0], speed = [1,2,1,2]

Output: 1

Explanation:

• The car at position 3 and the car at position 1 will form a single car fleet.
• The car at position 2 and the car at position 0 will also form a single car fleet.

Steps

1. Sort: Sort the target and speed arrays in descending order based on the target positions. This ensures we process cars from the furthest away to the closest.

2. Calculate Arrival Times: For each car, calculate the time it will take to reach the destination (position 0). This is given by target[i] / speed[i].

3. Detect Fleets: Iterate through the sorted arrays. Maintain a variable lastArrivalTime to track the arrival time of the last fleet encountered. If the current car's arrival time is greater than or equal to lastArrivalTime, it forms a new fleet. Otherwise, it joins the existing fleet.

4. Count Fleets: Increment a fleetCount variable every time a new fleet is detected.

Explanation

The sorting step is crucial because it allows us to process cars in the order they will potentially form fleets. If a faster car is behind a slower car, it will catch up and form a fleet. By processing from furthest to nearest, we can efficiently determine fleet formations. The arrival time calculation is straightforward. The comparison of arrival times determines whether a new fleet is formed or an existing fleet is extended.

Code

function carFleet(target: number[], speed: number[]): number {
    const n = target.length;
    if (n === 0) return 0;

    // Sort cars by target position in descending order
    const cars = Array.from({ length: n }, (_, i) => ({ target: target[i], speed: speed[i] }));
    cars.sort((a, b) => b.target - a.target);

    let fleetCount = 1;
    let lastArrivalTime = cars[0].target / cars[0].speed;

    for (let i = 1; i < n; i++) {
        const arrivalTime = cars[i].target / cars[i].speed;
        if (arrivalTime >= lastArrivalTime) {
            fleetCount++;
            lastArrivalTime = arrivalTime;
        }
    }

    return fleetCount;
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(N) in the worst case to store the cars array. The space usage is independent of the input size if we modify the input arrays in-place, but creating the cars array adds O(N) space complexity.