← Algorithmic Patterns
mediumStack

Car Fleet

Cars travel toward a target and cannot pass. When a faster car catches a slower one, they become a fleet at the slower speed. Count fleets arriving at the target; meeting exactly at the target also merges them.

LeetCode ↗

Work through the cases

3 examples

Input notation

Target on line 1; distinct starting positions on line 2; corresponding positive speeds on line 3. All positions are below the target.

Expected result

The fleet count.
Case 1

Input

10
0 4 8
2 1 1

Expected output

2
Case 2

Input

12
3
3

Expected output

1
Case 3

Input

10
0 5
2 1

Expected output

1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

A car closer to the target cannot be passed; a faster car behind catches up and joins the same fleet. n ≤ 10^5, so simulating overtakes is slow. Sort by position from the target backward and look at arrival times. A car slower than the fleet ahead starts a new fleet; otherwise it merges. The number of such leaders is the answer.

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        Integer[] idx = new Integer[n];
        Arrays.setAll(idx, i -> i);
        Arrays.sort(idx, (i, j) -> position[j] - position[i]);
        int ans = 0;
        double pre = 0;
        for (int i : idx) {
            double t = 1.0 * (target - position[i]) / speed[i];
            if (t > pre) {
                ++ans;
                pre = t;
            }
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.