Problem

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

Example 1:

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 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 each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Example 2:

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

Example 3:

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 each other 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 each other at 6. The fleet moves at speed 1 until it reaches target.

Solution

Method 1 - Using Kinematics, stack and sorting

As illustrated in the example, Vehicle 1 is closest to the target and will lead a fleet since no vehicle behind it can overtake it. Vehicle 2, starting farther away but moving faster, would ideally reach the target first if Vehicle 1 wasn’t ahead. However, Vehicle 2 will join the fleet led by Vehicle 1 upon catching up. Vehicle 3 arrives later (at t2 time) than the fleet in front and thus forms its own fleet.

We can take following steps:

  1. Sort the vehicles by their (position, speed) pairs.
  2. The first vehicle will form its own fleet. From the second vehicle onward, compare each vehicle’s ideal arrival time with the top of the stack, representing the latest arrival time of the current fleet.
  3. If a vehicle arrives earlier, it joins the existing fleet.
  4. Otherwise, it starts a new fleet, and its arrival time is added to the stack.
  5. The stack then contains the distinct arrival times, representing the number of fleets.

Code

Java
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        Car[] cars = new Car[n];
        
        for (int i = 0; i < n; i++) {
            cars[i] = new Car(position[i], (double) (target - position[i]) / speed[i]);
        }
        
        Arrays.sort(cars, (a, b) -> Double.compare(b.position, a.position));
        
        Stack<Double> stack = new Stack<>();
        
        for (Car car : cars) {
            if (stack.isEmpty() || car.time > stack.peek()) {
                stack.push(car.time);
            }
        }
        
        return stack.size();
    }
    
    class Car {
        int position;
        double time;
        
        Car(int position, double time) {
            this.position = position;
            this.time = time;
        }
    }
}
Python
class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        stack = []
        cars = sorted(zip(position, speed), reverse=True)
        
        for pos, vel in cars:
            time = (target - pos) / vel
            if not stack or time > stack[-1]:
                stack.append(time)
        
        return len(stack)

Method 2 - Using Sorting

Here is the approach:

  1. Calculate Arrival Times: For each car, calculate its time to reach the target using the formula (target - pos[i]) / speed[i].
  2. Create an Array of Tuples: Store each car’s position and calculated arrival time in an array of tuples.
  3. Sort the Cars by Position: Sort the array of tuples based on position in ascending order to process cars from farthest to closest.
  4. Track Fleets Using Arrival Time:
    • Initialize a variable cur to keep track of the current fleet’s arrival time.
    • Traverse the sorted array from the end:
      • If a car’s arrival time is greater than the cur (current fleet’s time), it starts a new fleet.
      • Otherwise, it joins the current fleet.
  5. Count Fleets: The number of times a new fleet is initiated during the traversal is the number of car fleets.

Code

Java
class Solution {
    public int carFleet(int target, int[] pos, int[] speed) {
        int n = pos.length;
        double[][] arrivalTimes = new double[n][2];
        
        // Calculate arrival times
        for (int i = 0; i < n; i++) {
            arrivalTimes[i] = new double[] {pos[i], (double)(target - pos[i]) / speed[i]};
        }
        
        // Sort the cars by their positions
        Arrays.sort(arrivalTimes, (a, b) -> Double.compare(a[0], b[0]));
        
        double cur = 0;
        int ans = 0;
        
        // Traverse the sorted array from the farthest car
        for (int i = n - 1; i >= 0; i--) {
            if (arrivalTimes[i][1] > cur) {
                cur = arrivalTimes[i][1];
                ans++;
            }
        }
        
        return ans;
    }
}
Python
class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        n = len(position)
        arrival_times = [(position[i], (target - position[i]) / speed[i]) for i in range(n)]
        
        # Sort the array by positions
        arrival_times.sort(key=lambda x: x[0])
        
        cur = 0.0
        ans = 0
        
        # Traverse the sorted list from the farthest car
        for pos, time in reversed(arrival_times):
            if time > cur:
                cur = time
                ans += 1
                
        return ans

Complexity

  • ⏰ Time complexity: O(n log n) due to sorting the array.
  • 🧺 Space complexity: O(n) for storing arrival times and positions of cars.

Method 3 - Using Treemap

Here is the approach:

  1. Calculate Arrival Times: Compute the time for each car to reach the target using the formula (target - pos[i]) / speed[i].
  2. Store in Map: Use a TreeMap to store the positions as keys and arrival times as values. The map is sorted in reverse order of positions automatically.
  3. Traverse Map:
    • Initialize a variable cur to track the current fleet’s arrival time.
    • Iterate through the values (arrival times) in the map:
      • If a car’s arrival time is greater than cur, initiate a new fleet.
      • Update cur to the current car’s arrival time.
  4. Count Fleets: Count the number of times a new fleet is initiated during the iteration.

Code

Java
class Solution {
    public int carFleet(int target, int[] pos, int[] speed) {
        Map<Integer, Double> map = new TreeMap<>(Collections.reverseOrder());
        
        // Calculate arrival times and store in TreeMap
        for (int i = 0; i < pos.length; i++) {
            map.put(pos[i], (double)(target - pos[i]) / speed[i]);
        }
        
        int res = 0;
        double cur = 0;
        
        // Iterate over the values in the TreeMap
        for (double time : map.values()) {
            if (time > cur) {
                cur = time;
                res++;
            }
        }
        
        return res;
    }
}
Python
class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Calculate arrival times and store in a sorted dictionary
        arrival_times = {pos: (target - pos) / speed for pos, speed in zip(position, speed)}
        sorted_arrival_times = collections.OrderedDict(sorted(arrival_times.items(), key=lambda item: item[0], reverse=True))
        
        res = 0
        cur = 0.0
        
        # Iterate over the values in the sorted dictionary
        for time in sorted_arrival_times.values():
            if time > cur:
                cur = time
                res += 1
        
        return res

Complexity

  • ⏰ Time complexity: O(n log n) due to sorting in the TreeMap.
  • 🧺 Space complexity: O(n) for storing arrival times in the map.