Car Fleet

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 cannot pass another car ahead of it — it can only catch up and then drive at the same speed as the car ahead.

A car fleet is a non-empty set of cars driving at the same position and speed. A single car is also a fleet. If a car catches up to a fleet the moment the fleet reaches the destination, it is part of that fleet.

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

Examples

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Sorting — sorting arrays of pairs by a custom key (descending position)
• Stack — using a stack to track the most recent valid state and compare with new entries
• Time-Distance Calculations — computing arrival time as (target − position) / speed
• Monotonic Stack intuition — understanding when to pop based on a comparison condition

1. Stack (Monotonic)

Intuition

The key insight is that a car behind cannot pass the car in front. So if a faster car starts behind a slower one, it will eventually catch up and be forced to slow down — they form a fleet.

We convert each car into its arrival time at the target: time = (target − position) / speed. Then, if we process cars from closest-to-target to farthest, a car forms a new fleet only if it takes longer to arrive than the car in front of it. If it arrives in the same time or sooner, it catches up and merges with that fleet.

A stack naturally tracks the active fleets. We push each car's arrival time. If the new top is ≤ the element below it, the car merges into the fleet ahead — we pop it. What remains on the stack is one entry per distinct fleet.

Algorithm

• Pair each car's position with its speed.
• Sort pairs in descending order of position (closest to target first).
• For each car, compute time = (target − p) / s and push onto the stack.
• If stack[-1] ≤ stack[-2], the car catches up — pop it (it joins the fleet ahead).
• Return len(stack) — the number of distinct fleets.

2. Iteration (No Stack)

Intuition

After sorting cars from closest to farthest from the target, we only need to track the arrival time of the most recent fleet — prevTime. A car forms a new fleet only if it takes longer than prevTime. If it takes the same time or less, it will catch up and merge, so we ignore it.

This removes the need for a stack entirely. We just scan left-to-right through the sorted pairs and count how many times we see a car that is strictly slower (larger arrival time) than the fleet ahead of it.

Algorithm

• Sort (position, speed) pairs descending by position.
• Initialise fleets = 1 and prevTime from the first (closest) car.
• For each remaining car: compute its currTime.
• If currTime > prevTime: it cannot catch up → new fleet, increment count, update prevTime.
• Otherwise: it merges → do nothing.
• Return 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)):
            currTime = (target - pair[i][0]) / pair[i][1]
            if currTime > prevTime:
                fleets += 1
                prevTime = currTime
        return fleets

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] = new int[]{position[i], speed[i]};
        Arrays.sort(pair, (a, b) -> 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;
    }
}

Time Complexity: O(n log n) — dominated by sorting.
Space Complexity: O(n) — for the pairs array.

Common Pitfalls

Sorting in the Wrong Order

Sorting by position in ascending order (farthest from target first) breaks the algorithm. Cars must be processed from closest to the target first, because only a car behind can catch up to one in front — never the other way around. Ascending sort causes incorrect merging decisions.

# Wrong: ascending order (farthest from target first)
pair.sort()

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

Using Strict Less Than Instead of Less Than or Equal

Using stack[-1] < stack[-2] misses the case where two cars arrive at exactly the same time. A car that arrives simultaneously with the fleet ahead is still part of that fleet — the problem statement explicitly says so. Always use <=.

# Wrong: misses equal arrival times
if stack[-1] < stack[-2]:
    stack.pop()

# Correct: merge when same time or faster
if stack[-1] <= stack[-2]:
    stack.pop()

Integer Division in Statically-Typed Languages

In Java or C++, dividing two integers performs integer division which truncates the decimal. Arrival times are often fractional (e.g., 5/3 ≈ 1.67). Using integer division collapses distinct arrival times together, causing wrong fleet counts. Always cast to double or float before dividing.

// Wrong: integer division truncates
int time = (target - position) / speed;

// Correct: cast to double for precise fractional time
double time = (double)(target - position) / speed;