Car Fleet

Problem Statement

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 $i^{th}$ car and speed[i] is the speed of the $i^{th}$ 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.

Example:
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 car starting at 5 (speed 1) does not catch up to any other car, so it is a fleet by itself.
• The cars starting at 3 (speed 3) and 0 (speed 1) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
• We have 3 car fleets arriving at the destination.

Approach: Stack / Sorting

The key insight is to look at the cars from closest to the target to furthest. A car further back can only join a fleet ahead of it if it reaches the target in less than or equal time compared to the fleet ahead.

1. Combine the position and speed of each car into pairs so they stay linked.
2. Sort the cars in descending order based on their starting position (cars closest to the target come first).
3. Initialize an empty stack to keep track of the arrival times of the fleets.
4. Iterate through the sorted cars:
   • Calculate the time it takes for the current car to reach the target: (target - position) / speed.
   • If the stack is empty, push this time onto the stack (this is our first fleet).
   • If the stack is not empty, compare the current car’s time with the arrival time of the fleet at the top of the stack.
     • If the current car’s time is $\le$ the top of the stack, it means the current car is faster and will catch up to the fleet ahead of it. It joins that fleet, so we do nothing (it assumes the slower speed of the fleet ahead).
     • If the current car’s time is $>$ the top of the stack, it means it’s too slow to catch up. It forms a brand new fleet, so we push its time onto the stack.
5. At the end, the number of items in the stack represents the number of independent fleets.

Solution

/**
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
function carFleet(target, position, speed) {
    // Pair positions and speeds together
    const cars = [];
    for (let i = 0; i < position.length; i++) {
        cars.push({ pos: position[i], spd: speed[i] });
    }
    
    // Sort cars based on position in descending order
    cars.sort((a, b) => b.pos - a.pos);
    
    const stack = [];
    
    for (let i = 0; i < cars.length; i++) {
        const timeToTarget = (target - cars[i].pos) / cars[i].spd;
        
        // If stack is empty or this car takes longer than the fleet ahead, it forms a new fleet
        if (stack.length === 0 || timeToTarget > stack[stack.length - 1]) {
            stack.push(timeToTarget);
        }
        // Otherwise, it catches up and joins the fleet ahead, so we don't push it
    }
    
    return stack.length;
}

Complexity Analysis

• Time Complexity: $O(n \log n)$ where $n$ is the number of cars. Creating the pairs takes $O(n)$, sorting them takes $O(n \log n)$, and iterating through them with the stack takes $O(n)$. The dominating factor is the sorting step.
• Space Complexity: $O(n)$ to store the array of car pairs and the stack. In the worst case, every car forms its own fleet, and the stack will store $n$ times.