Problem Description

You are given a target position target on a straight road and two integer arrays position and speed, both of length n, where position[i] is the starting position of the i-th car, and speed[i] is its speed (in the same units as the target).

All cars are driving towards the target in the same direction. A car cannot pass another car ahead of it, but it can catch up and form a fleet with cars in front of it. When a car catches up to another car or fleet, it joins that fleet and they travel together at the same speed (the slowest speed in the fleet).
A car fleet is a group of cars that arrive at the destination at the same time.

Your task is to compute how many car fleets will arrive at the target. Each car belongs to exactly one fleet, and a fleet may consist of just one car.

Constraints:

• There is only one valid answer for each input.
• Each car can belong to only one fleet, and cars cannot overtake each other.
• 0 < position.length == speed.length <= 10^4
• 0 < position[i] < target <= 10^6
• All positions are unique.
• Speeds are positive integers.

Thought Process

At first glance, you might try to simulate each car's journey step by step, tracking their positions as they move and merge. However, this would be inefficient and unnecessarily complex.

Instead, notice that the key insight is to focus on when each car would reach the target if it were alone. If a faster car starts behind a slower car, it may catch up and join the slower car's fleet before reaching the target. But since cars cannot pass each other, once they merge, they travel together at the slower speed.

By calculating the time each car would take to reach the target, and processing cars from the closest to the farthest from the target, we can efficiently determine when fleets form. This avoids brute-force simulation and leverages sorting and simple iteration.

Solution Approach

• Step 1: Calculate time to target for each car.
  For each car, compute time = (target - position[i]) / speed[i]. This gives the time each car would take to reach the target if it did not join a fleet.
• Step 2: Pair positions and times, then sort by position descending.
  Since cars can't pass each other, we process cars from closest to the target to farthest. Sort the cars by position in descending order.
• Step 3: Iterate and count fleets.
  Starting from the car closest to the target, iterate through the sorted list:
  • If a car's time to the target is greater than the time of the fleet ahead, it can't catch up and forms a new fleet.
  • If its time is less than or equal to the fleet ahead, it will join that fleet.
  We use a stack or a simple counter to track the number of fleets.
• Why this works:
  By processing from closest to farthest, we always know whether a car will join a fleet ahead or form a new one, without simulating every movement.

Example Walkthrough

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

1. Calculate times:
   • Car at 10: (12-10)/2 = 1
   • Car at 8: (12-8)/4 = 1
   • Car at 0: (12-0)/1 = 12
   • Car at 5: (12-5)/1 = 7
   • Car at 3: (12-3)/3 = 3
2. Sort by position descending:
   • 10 (1), 8 (1), 5 (7), 3 (3), 0 (12)
3. Process cars:
   • Start with car at 10 (time 1): forms a new fleet (fleet count = 1)
   • Car at 8 (time 1): time == previous, merges into same fleet (fleet count = 1)
   • Car at 5 (time 7): time > 1, forms a new fleet (fleet count = 2)
   • Car at 3 (time 3): time < 7, merges into fleet at 5 (fleet count = 2)
   • Car at 0 (time 12): time > 7, forms a new fleet (fleet count = 3)
4. Final answer: 3 fleets arrive at the target.

Time and Space Complexity

• Brute-force approach:
  Simulating each car's movement and fleet formation step-by-step could take up to O(n²) time, which is inefficient for large inputs.
• Optimized approach:
  • Time Complexity: O(n log n) due to sorting the cars by position. The rest of the algorithm is O(n).
  • Space Complexity: O(n) to store the position-time pairs and any stack or list used during iteration.
• This makes the solution efficient and scalable for large input sizes.

Summary

The Car Fleet problem is elegantly solved by shifting the perspective from simulating car movements to analyzing their arrival times. By sorting cars by position and comparing times to the target, we can efficiently count fleets without unnecessary computation. The key insight is that a car can only form a new fleet if it cannot catch up to the fleet ahead. Sorting and a single pass yield an O(n log n) solution that is both simple and powerful.

Code Implementation

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        fleets = 0
        curr_time = 0
        for pos, spd in cars:
            time = (target - pos) / spd
            if time > curr_time:
                fleets += 1
                curr_time = time
        return fleets
      

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<int, double>> cars;
        int n = position.size();
        for (int i = 0; i < n; ++i) {
            cars.push_back({position[i], (double)(target - position[i]) / speed[i]});
        }
        sort(cars.rbegin(), cars.rend());
        int fleets = 0;
        double curr_time = 0;
        for (auto& car : cars) {
            if (car.second > curr_time) {
                fleets++;
                curr_time = car.second;
            }
        }
        return fleets;
    }
};
      

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        double[][] cars = new double[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }
        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
        int fleets = 0;
        double curr_time = 0;
        for (int i = 0; i < n; i++) {
            if (cars[i][1] > curr_time) {
                fleets++;
                curr_time = cars[i][1];
            }
        }
        return fleets;
    }
}
      

var carFleet = function(target, position, speed) {
    let cars = position.map((pos, i) => [pos, (target - pos) / speed[i]]);
    cars.sort((a, b) => b[0] - a[0]);
    let fleets = 0;
    let currTime = 0;
    for (let [pos, time] of cars) {
        if (time > currTime) {
            fleets++;
            currTime = time;
        }
    }
    return fleets;
};