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 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 can never pass another car ahead of it, but it can catch up to it and drive write behind it at the same speed. The distance between these two cars is ignored (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 another car right at the destination point, they will still be considered as one car fleet.

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

Examples

Constraints

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

Sorting by Starting Position

If a car starts closer to the destination, it acts as a bottleneck for any faster car behind it. This means we can evaluate fleets by sorting the cars by their starting position in descending order (from closest to farthest from the destination). For each car, calculate the time it takes to reach the destination independently: time = (target - position) / speed. We iterate through the sorted cars. If a car behind takes less time or equal time to reach the destination than the car fleet in front of it, it will catch up and merge into the front car’s fleet. If it takes more time, it starts a new independent fleet.

Solution 1: Descending Position Sorting with Stack

Sort cars by position and scan backward while tracking arriving times.

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    private static class Car {
        int pos;
        double time;
        Car(int pos, double time) {
            this.pos = pos;
            this.time = time;
        }
    }

    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]);
        }

        // Sort by starting position descending
        Arrays.sort(cars, (a, b) -> Integer.compare(b.pos, a.pos));

        int fleets = 0;
        double lastTime = 0.0;
        for (Car car : cars) {
            if (car.time > lastTime) {
                fleets++;
                lastTime = car.time; // starts a new fleet
            }
        }
        return fleets;
    }
}

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        # Pair position and arrival time, then sort by position descending
        cars = sorted(zip(position, speed), key=lambda x: x[0], reverse=True)
        
        fleets = 0
        last_time = 0.0
        for pos, spd in cars:
            time = (target - pos) / spd
            if time > last_time:
                fleets += 1
                last_time = time  # starts a new fleet
        return fleets

#include <vector>
#include <algorithm>

class Solution {
public:
    int carFleet(int target, std::vector<int>& position, std::vector<int>& speed) {
        int n = position.size();
        std::vector<std::pair<int, double>> cars(n);
        for (int i = 0; i < n; i++) {
            cars[i] = {position[i], (double)(target - position[i]) / speed[i]};
        }

        // Sort by position in descending order
        std::sort(cars.begin(), cars.end(), [](const auto& a, const auto& b) {
            return a.first > b.first;
        });

        int fleets = 0;
        double lastTime = 0.0;
        for (int i = 0; i < n; i++) {
            if (cars[i].second > lastTime) {
                fleets++;
                lastTime = cars[i].second; // starts a new fleet
            }
        }
        return fleets;
    }
};

Complexity Analysis

• Time Complexity: O(n log n) due to the sorting step. The subsequent linear scan takes O(n) time.
• Space Complexity: O(n) auxiliary space to store the paired position and time coordinates.

Where It Breaks

If cars can pass each other (e.g. multi-lane highways), the ordering constraint breaks. However, because the lane is strictly single-lane and passing is forbidden, this bottleneck behavior holds.

Common Mistakes

• Incorrect sorting direction: Sorting by position in ascending order, which evaluates the cars from back to front instead of front to back.
• Using integer division for times: Calculating time as an integer (target - pos) / speed. If one car takes 2.5 hours and another takes 2.1 hours, integer division will round both to 2 and incorrectly merge them into a single fleet.

Frequently Asked Questions

Why does sorting by position help? Because cars cannot pass each other, the car closest to the destination sets the baseline arrival time. Any car behind it that arrives faster will be blocked by it and forced to join its fleet.

Does a single car count as a fleet? Yes, the problem states that a single car is considered a fleet of size 1.

← All Problems