8.7 Car Fleet

8.7.1 Problem Metadata

8.7.2 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 arrays 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 cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the destination, it will still be considered as part of the car fleet.

Return the number of car fleets that will arrive at the destination.

8.7.3 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 at 12.
  The car at 10 will take (12 - 10) / 2 = 1 hour to reach the target.
  The car at 8 will take (12 - 8) / 4 = 1 hour to reach the target.
  They both arrive at the target at the same time, so they become a fleet.
- The car starting at 0 (speed 1) doesn't 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.
  The car at 5 will take (12 - 5) / 1 = 7 hours to reach the target.
  The car at 3 will take (12 - 3) / 3 = 3 hours to reach position 6, then slows down to match the car ahead.
  They arrive at the target together, so they become a fleet.

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, so it forms 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 at 4.
  The car at 0 will take (100 - 0) / 4 = 25 hours to reach the target.
  The car at 2 will take (100 - 2) / 2 = 49 hours to reach the target.
- The car starting at 4 (speed 1) will take (100 - 4) / 1 = 96 hours to reach the target.
  It catches up to the fleet at the destination and forms one fleet.

8.7.4 Constraints

  • n == position.length == speed.length
  • \(1 \le n \le 10^5\)
  • \(0 < target \le 10^6\)
  • \(0 \le position[i] < target\)
  • All the values of position are unique.
  • \(0 < speed[i] \le 10^6\)

8.7.5 Solution - Stack with Sorting

8.7.5.1 Walkthrough

The key insight is to avoid simulating the cars’ movement tick-by-tick, which would be too slow. Instead, calculate the time each car needs to reach the target and determine which cars will form fleets based on these times.

Core Observations:

  1. Time to reach target: For each car, time = (target - position) / speed
  2. Cars closer to target dictate fleet formation: Process cars from closest to target to furthest
  3. Fleet formation rule:
    • If a car behind takes less time than the car ahead, it will catch up and join that fleet
    • If a car behind takes more time, it cannot catch up and becomes a new fleet

Algorithm:

  1. Create pairs of (position, time_to_target) for each car
  2. Sort cars by position in descending order (closest to target first)
  3. Iterate through sorted cars:
    • If current car’s time > previous car’s time → it’s a new fleet (cannot catch up)
    • If current car’s time \(\le\) previous car’s time → it joins the previous fleet (catches up)

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

  1. Calculate times:

    • Position 10, speed 2: time = (12-10)/2 = 1.0 hour
    • Position 8, speed 4: time = (12-8)/4 = 1.0 hour
    • Position 0, speed 1: time = (12-0)/1 = 12.0 hours
    • Position 5, speed 1: time = (12-5)/1 = 7.0 hours
    • Position 3, speed 3: time = (12-3)/3 = 3.0 hours

  2. Sort by position (descending): [(10, 1.0), (8, 1.0), (5, 7.0), (3, 3.0), (0, 12.0)]

  3. Process cars from front to back:

    • Car at pos 10 (time 1.0): 1.0 > 0 → Fleet 1 (prevTime = 1.0)
    • Car at pos 8 (time 1.0): 1.0 ≤ 1.0 → joins Fleet 1 (arrives at same time)
    • Car at pos 5 (time 7.0): 7.0 > 1.0 → Fleet 2 (slower, becomes new leader, prevTime = 7.0)
    • Car at pos 3 (time 3.0): 3.0 ≤ 7.0 → joins Fleet 2 (catches up to slower car ahead)
    • Car at pos 0 (time 12.0): 12.0 > 7.0 → Fleet 3 (slowest, can’t catch up)

  4. Result: 3 fleets

8.7.5.2 Analysis

  • Time Complexity: O(n log n) where n is the number of cars
    • Creating the cars array: O(n)
    • Sorting by position: O(n log n)
    • Iterating to count fleets: O(n)
    • Overall: O(n log n)
  • Space Complexity: O(n)
    • Storage for the cars array with position and time pairs: O(n)
    • Sorting space (depends on implementation): O(log n) to O(n)
    • Overall: O(n)

8.7.5.3 Implementation Steps

  1. Create a 2D array cars where each element stores [position, time_to_target]
  2. Calculate time_to_target = (target - position) / speed for each car
  3. Sort the cars array by position in descending order (closest to target first)
  4. Initialize result = 0 (fleet counter) and prevTime = 0 (time of previous fleet leader)
  5. Iterate through sorted cars:
    • If currTime > prevTime: increment result, update prevTime = currTime
    • Otherwise: car joins the previous fleet (no action needed)
  6. Return result

8.7.5.4 Code - Java

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int len = position.length;

        // Create array of [position, time to target] pairs
        double[][] cars = new double[len][2];
        for (int i = 0; i < len; i++) {
            cars[i][0] = (double)position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }

        // Sort by position (descending - closest to target first)
        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));

        // Count fleets using stack concept
        int result = 0;
        double prevTime = 0;

        for(double[] car : cars) {
            double currTime = car[1];

            // If current car takes longer than previous fleet, it's a new fleet
            if(currTime > prevTime) {
                result++;
                prevTime = currTime;
            }
            // Otherwise, current car belongs to the same fleet
        }

        return result;
    }
}

8.7.5.5 Code - Go

import "sort"

func carFleet(target int, position []int, speed []int) int {
    len := len(position)

    cars := make([][]float64, len)
    for i := range cars {
        cars[i] = make([]float64, 2)

        cars[i][0] = float64(position[i])
        cars[i][1] = float64(target - position[i]) / float64(speed[i])
    }

    // Sort by position (descending - closest to target first)
    sort.Slice(cars, func(i int, j int) bool {
        return cars[i][0] > cars[j][0]
    })

    prevTime := float64(0)
    result := 0

    for _, car := range cars {
        currTime := car[1]

        if currTime > prevTime {
            result++
            prevTime = currTime
        }
    }

    return result
}