853. Car Fleet - Explanation

Description

There are n cars traveling to the same destination on a one-lane highway.

You are given two arrays of integers position and speed, both of length n.

position[i] is the position of the ith car (in miles)
speed[i] is the speed of the ith car (in miles per hour)

The destination is at position target miles.

A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.

A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.

If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.

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

Example 1:

Input: target = 10, position = [1,4], speed = [3,2]

Output: 1

Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, meeting each other at 10, the destination.

Example 2:

Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1]

Output: 3

Explanation: The cars starting at 4 and 7 become a fleet at position 10. The cars starting at 1 and 0 never catch up to the car ahead of them. Thus, there are 3 car fleets that will arrive at the destination.

Constraints:

n == position.length == speed.length.
1 <= n <= 1000
0 < target <= 1000
0 < speed[i] <= 100
0 <= position[i] < target
All the values of position are unique.

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(nlogn) time and O(n) space, where n is the size of the input array.

Hint 1

First draw a picture of all the points which represents the positions and respective speeds of the cars. It is appropriate to represent the position and speed of each car as an array, where each cell corresponds to a car. It is also logical to sort this array based on the positions in descending order. Why?

Hint 2

Because a car can only form a fleet with another car that is ahead of it, sorting the array in descending order ensures clarity about the final speed of each car. Sorting in ascending order would create ambiguity, as the next car might form a fleet with another car while reaching the target, making it difficult to determine its final speed.

Hint 3

Calculating the time for a car to reach the target is straightforward and can be done using the formula: time = (target - position) / speed. Now, it becomes easy to identify that two cars will form a fleet if and only if the car ahead has a time that is greater than or equal to the time of the car behind it. How can we maintain the total number of fleets happened while going through the array? Maybe a data structure is helpful.

Hint 4

We can use a stack to maintain the times of the fleets. As we iterate through the array (sorted in descending order of positions), we compute the time for each car to reach the target and check if it can form a fleet with the car ahead. If the current car's time is less than or equal to the top of the stack, it joins the same fleet. Otherwise, it forms a new fleet, and we push its time onto the stack. The length of the stack at the end represents the total number of fleets formed.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Sorting arrays of pairs/tuples by custom criteria
Stack - Using a stack to track and merge elements based on conditions
Time-Distance Calculations - Computing arrival times from position, speed, and target

1. Stack

Intuition

Cars that start closer to the target are processed first.
For each car, we compute the time it will take to reach the target.
If a car behind reaches the target no faster than the car in front, it will eventually catch up and join the same fleet.
So we only keep the car’s time if it forms a new fleet; otherwise, it merges with the previous one.
Using a stack helps us easily compare each car’s time with the fleet ahead of it.

Algorithm

Pair each car's position with its speed.
Sort the cars in descending order of position (closest to target first).
For each car:
- Compute the time it takes to reach the target.
- Push this time onto a stack.
- If the new car’s time is less than or equal to the time before it,
  it catches up and merges with that fleet → pop it from the stack.
The number of remaining times in the stack equals the number of fleets.
Return the stack size.

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pair = [(p, s) for p, s in zip(position, speed)]
        pair.sort(reverse=True)
        stack = []
        for p, s in pair:  # Reverse Sorted Order
            stack.append((target - p) / s)
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop()
        return len(stack)

public class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int[][] pair = new int[position.length][2];
        for (int i = 0; i < position.length; i++) {
            pair[i][0] = position[i];
            pair[i][1] = speed[i];
        }
        Arrays.sort(pair, (a, b) -> Integer.compare(b[0], a[0]));
        Stack<Double> stack = new Stack<>();
        for (int[] p : pair) {
            stack.push((double) (target - p[0]) / p[1]);
            if (stack.size() >= 2 &&
                stack.peek() <= stack.get(stack.size() - 2))
            {
                stack.pop();
            }
        }
        return stack.size();
    }
}

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<int, int>> pair;
        for (int i = 0; i < position.size(); i++) {
            pair.push_back({position[i], speed[i]});
        }
        sort(pair.rbegin(), pair.rend());
        vector<double> stack;
        for (auto& p : pair) {
            stack.push_back((double)(target - p.first) / p.second);
            if (stack.size() >= 2 &&
                stack.back() <= stack[stack.size() - 2])
            {
                stack.pop_back();
            }
        }
        return stack.size();
    }
};

class Solution {
    /**
     * @param {number} target
     * @param {number[]} position
     * @param {number[]} speed
     * @return {number}
     */
    carFleet(target, position, speed) {
        let pair = position.map((p, i) => [p, speed[i]]);
        pair.sort((a, b) => b[0] - a[0]);
        let stack = [];
        for (let [p, s] of pair) {
            stack.push((target - p) / s);
            if (
                stack.length >= 2 &&
                stack[stack.length - 1] <= stack[stack.length - 2]
            ) {
                stack.pop();
            }
        }
        return stack.length;
    }
}

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int[][] pair = new int[position.Length][];
        for (int i = 0; i < position.Length; i++) {
            pair[i] = new int[] { position[i], speed[i] };
        }
        Array.Sort(pair, (a, b) => b[0].CompareTo(a[0]));
        Stack<double> stack = new Stack<double>();
        foreach (var p in pair) {
            stack.Push((double)(target - p[0]) / p[1]);
            if (stack.Count >= 2 && stack.Peek() <= stack.ElementAt(1)) {
                stack.Pop();
            }
        }
        return stack.Count;
    }
}

class Solution {
    fun carFleet(target: Int, position: IntArray, speed: IntArray): Int {
        val pair = position.zip(speed).sortedByDescending { it.first }
        val stack = mutableListOf<Double>()

        for ((p, s) in pair) {
            val time = (target - p).toDouble() / s
            stack.add(time)
            if (stack.size >= 2 && stack[stack.size - 1] <= stack[stack.size - 2]) {
                stack.removeAt(stack.size - 1)
            }
        }

        return stack.size
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Iteration

Intuition

After sorting cars from closest to the target to farthest, we calculate how long each one needs to reach the target.
A car forms a new fleet only if it takes longer than the fleet in front of it.
If it takes the same time or less, it will eventually catch up and merge into that fleet.
So instead of using a stack, we just keep track of the most recent fleet time.

Algorithm

Pair each car’s position with its speed and sort descending by position.
Start with the first car forming the first fleet.
Keep track of the fleet's time (prevTime) - the time of the car closest to the target.
For each remaining car:
- Compute its time to reach the target.
- If this time is greater than prevTime, it cannot catch up and forms a new fleet.
  - Increase fleet count.
  - Update prevTime to this new time.
- Otherwise, it merges with the existing fleet and do nothing.
Return the number of fleets.

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pair = [(p, s) for p, s in zip(position, speed)]
        pair.sort(reverse=True)

        fleets = 1
        prevTime = (target - pair[0][0]) / pair[0][1]
        for i in range(1, len(pair)):
            currCar = pair[i]
            currTime = (target - currCar[0]) / currCar[1]
            if currTime > prevTime:
                fleets += 1
                prevTime = currTime
        return fleets

public class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        int[][] pair = new int[n][2];
        for (int i = 0; i < n; i++) {
            pair[i][0] = position[i];
            pair[i][1] = speed[i];
        }
        Arrays.sort(pair, (a, b) -> Integer.compare(b[0], a[0]));

        int fleets = 1;
        double prevTime = (double)(target - pair[0][0]) / pair[0][1];
        for (int i = 1; i < n; i++) {
            double currTime = (double)(target - pair[i][0]) / pair[i][1];
            if (currTime > prevTime) {
                fleets++;
                prevTime = currTime;
            }
        }
        return fleets;
    }
}

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        vector<pair<int, int>> pair;
        for (int i = 0; i < n; i++) {
            pair.push_back({position[i], speed[i]});
        }
        sort(pair.rbegin(), pair.rend());

        int fleets = 1;
        double prevTime = (double)(target - pair[0].first) / pair[0].second;
        for (int i = 1; i < n; i++) {
            double currTime = (double)(target - pair[i].first) / pair[i].second;
            if (currTime > prevTime) {
                fleets++;
                prevTime = currTime;
            }
        }
        return fleets;
    }
};

class Solution {
    /**
     * @param {number} target
     * @param {number[]} position
     * @param {number[]} speed
     * @return {number}
     */
    carFleet(target, position, speed) {
        let pair = position.map((p, i) => [p, speed[i]]);
        pair.sort((a, b) => b[0] - a[0]);

        let fleets = 1;
        let prevTime = (target - pair[0][0]) / pair[0][1];
        for (let i = 1; i < pair.length; i++) {
            let currTime = (target - pair[i][0]) / pair[i][1];
            if (currTime > prevTime) {
                fleets++;
                prevTime = currTime;
            }
        }
        return fleets;
    }
}

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
        int[][] pair = new int[n][];
        for (int i = 0; i < n; i++) {
            pair[i] = new int[] { position[i], speed[i] };
        }
        Array.Sort(pair, (a, b) => b[0].CompareTo(a[0]));

        int fleets = 1;
        double prevTime = (double)(target - pair[0][0]) / pair[0][1];
        for (int i = 1; i < n; i++) {
            double currTime = (double)(target - pair[i][0]) / pair[i][1];
            if (currTime > prevTime) {
                fleets++;
                prevTime = currTime;
            }
        }
        return fleets;
    }
}

class Solution {
    fun carFleet(target: Int, position: IntArray, speed: IntArray): Int {
        val pair = position.zip(speed).sortedByDescending { it.first }

        var fleets = 1
        var prevTime = (target - pair[0].first).toDouble() / pair[0].second
        for (i in 1 until pair.size) {
            val (p, s) = pair[i]
            val currTime = (target - p).toDouble() / s
            if (currTime > prevTime) {
                fleets++
                prevTime = currTime
            }
        }

        return fleets
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

Common Pitfalls

Sorting in the Wrong Order

Sorting cars by position in ascending order (farthest from target first) instead of descending order causes incorrect fleet merging. Cars must be processed from closest to the target first, since a car behind can only merge with the fleet ahead of it.

# Wrong: ascending order
pair.sort()
# Correct: descending order (closest to target first)
pair.sort(reverse=True)

Using Strict Less Than for Fleet Merging

Using < instead of <= when comparing arrival times misses the case where two cars arrive at exactly the same time. If a car behind arrives at the same time or earlier than the car ahead, it joins that fleet.

# Wrong: misses equal arrival times
if stack[-1] < stack[-2]:
# Correct: cars arriving at same time merge
if stack[-1] <= stack[-2]:

Integer Division Instead of Float Division

In languages like Java or C++, dividing two integers results in integer division, which truncates the decimal part. Since arrival times are often fractional, this leads to incorrect comparisons and wrong fleet counts.

// Wrong: integer division truncates
int time = (target - position) / speed;
// Correct: cast to double for precise time
double time = (double)(target - position) / speed;