853. Car Fleet

Problem Description

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 as one car fleet. Return the number of car fleets that will arrive at the destination.

Examples:

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 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 at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

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

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 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 at 6.
The fleet moves at speed 1 until the destination.

Constraints:

• n == position.length == speed.length
• 1 ≤ n ≤ 10⁵
• 0 < target ≤ 10⁶
• 0 ≤ position[i] < target
• All the values of position are unique
• 0 < speed[i] ≤ 10⁶

Python Solution

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Create pairs of position and time to reach target
        pairs = [(p, (target - p) / s) for p, s in zip(position, speed)]
        # Sort by position in descending order
        pairs.sort(reverse=True)
        
        stack = []
        for _, time in pairs:
            # If current car takes longer time than the car in front
            # it will never catch up and form a new fleet
            if not stack or time > stack[-1]:
                stack.append(time)
        
        return len(stack)

Implementation Notes:

• Uses monotonic stack approach
• Time complexity: O(n log n)
• Space complexity: O(n)

Java Solution

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        double[][] cars = new double[n][2];
        
        // Create array of [position, time to reach target]
        for (int i = 0; i < n; i++) {
            cars[i] = new double[] {position[i], (double)(target - position[i]) / speed[i]};
        }
        
        // Sort by position in descending order
        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
        
        int fleets = 0;
        double slowest = 0;
        
        // Check each car from right to left
        for (double[] car : cars) {
            if (car[1] > slowest) {
                slowest = car[1];
                fleets++;
            }
        }
        
        return fleets;
    }
}

C++ Solution

class Solution {
public:
    int carFleet(int target, vector& position, vector& speed) {
        int n = position.size();
        vector> cars;
        
        // Create pairs of position and time to reach target
        for (int i = 0; i < n; i++) {
            double time = (double)(target - position[i]) / speed[i];
            cars.push_back({position[i], time});
        }
        
        // Sort by position in descending order
        sort(cars.rbegin(), cars.rend());
        
        int fleets = 0;
        double slowest = 0;
        
        for (const auto& car : cars) {
            if (car.second > slowest) {
                slowest = car.second;
                fleets++;
            }
        }
        
        return fleets;
    }
};

JavaScript Solution

/**
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function(target, position, speed) {
    const n = position.length;
    const cars = [];
    
    // Create array of [position, time to reach target]
    for (let i = 0; i < n; i++) {
        cars.push([position[i], (target - position[i]) / speed[i]]);
    }
    
    // Sort by position in descending order
    cars.sort((a, b) => b[0] - a[0]);
    
    const stack = [];
    for (const [_, time] of cars) {
        if (!stack.length || time > stack[stack.length - 1]) {
            stack.push(time);
        }
    }
    
    return stack.length;
};

C# Solution

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
        (int pos, double time)[] cars = new (int pos, double time)[n];
        
        // Create array of position and time to reach target
        for (int i = 0; i < n; i++) {
            cars[i] = (position[i], (double)(target - position[i]) / speed[i]);
        }
        
        // Sort by position in descending order
        Array.Sort(cars, (a, b) => b.pos.CompareTo(a.pos));
        
        int fleets = 0;
        double slowest = 0;
        
        foreach (var car in cars) {
            if (car.time > slowest) {
                slowest = car.time;
                fleets++;
            }
        }
        
        return fleets;
    }
}

Implementation Notes:

• Uses sorting and linear traversal
• Time complexity: O(n log n)
• Space complexity: O(n)