Car Fleet (LC 853)

Problem Statement

There are n cars going in the same direction toward a destination at position target. Car i starts at position[i] with constant speed speed[i]. A car can never pass another car ahead of it; if it catches up, it slows to match (forming a fleet). A fleet can be a single car. Fleets that arrive together count as one fleet. Return the number of fleets that arrive at the destination.

Example 1:

Input:  target = 12,
        position = [10, 8, 0, 5, 3],
        speed = [2, 4, 1, 1, 3]
Output: 3
Explanation: The car at position 10 reaches target first. The cars at 8 and 3 form a fleet ending at position 12. The cars at 0 and 5 form another fleet.

Example 2:

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

Constraints:

• n == position.length == speed.length
• 1 <= n <= 10^5
• 0 < target <= 10^6
• 0 < position[i] < target, all distinct.
• 0 < speed[i] <= 10^6

Difficulty: Medium

---

Pattern Recognition

• Input structure: 1D positions and speeds.
• What are we counting? distinct arrival groups at a common destination.
• Pattern: sort by position descending (closest to target first), scan once tracking arrival times with a monotonic comparison.
• Why: a car behind can never overtake the car ahead. So the question reduces to: processing cars front-to-back, does each car's arrival time exceed the time of the car it would merge into? If yes, it forms a new fleet; if no, it joins.

---

Approach

Brute Force

Simulate every timestep. Impractical for continuous positions and speeds.

Optimal — Sort by Position Descending, Track Max Arrival Time

Key Insight: Compute each car's unblocked arrival time t_i = (target - position_i) / speed_i. Sort cars by position descending. Scan; maintain maxT = the slowest arrival time seen so far among closer-to-target cars. A car forms a new fleet iff its t > maxT (it truly arrives later, not overtaken and not merged). Otherwise update nothing — it merges into the fleet ahead.

pairs = sorted by position descending
maxT = 0
fleets = 0
for (pos, spd) in pairs:
    t = (target - pos) / spd
    if t > maxT:
        fleets++
        maxT = t
    // else: caught up to fleet ahead, does not increase count
return fleets

Time: O(n log n) for sorting, O(n) for scan. Space: O(n).

Why this works: sorting front-to-back means when we examine car i, every car ahead is already accounted for, and its arrival time is ≤ maxT (because maxT is the slowest-arrival so far, which becomes the time at which the fleet actually reaches target). If t_i > maxT, car i is slower, cannot catch up, forms new fleet. Otherwise it catches up and merges.

---

Walkthrough

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

Compute times:

• (10, 2): t = (12-10)/2 = 1
• (8, 4): t = 4/4 = 1
• (0, 1): t = 12/1 = 12
• (5, 1): t = 7/1 = 7
• (3, 3): t = 9/3 = 3

Sort by position descending: [(10,2), (8,4), (5,1), (3,3), (0,1)] with times [1, 1, 7, 3, 12].

pos	t	maxT before	fleets before	Decision
10	1	0	0	1 > 0 → fleets=1, maxT=1
8	1	1	1	1 > 1? no (not strictly greater). Merge.
5	7	1	1	7 > 1 → fleets=2, maxT=7
3	3	7	2	3 > 7? no. Merge.
0	12	7	2	12 > 7 → fleets=3, maxT=12

Answer: 3. Matches expected.

Notice (8, 4) has t=1 which is equal to the fleet ahead — the strict > matters: equal means they arrive together = same fleet.

---

Implementation

TypeScript

function carFleet(target: number, position: number[], speed: number[]): number {
    const n = position.length;
    const cars: [number, number][] = [];
    for (let i = 0; i < n; i++) cars.push([position[i], speed[i]]);
    cars.sort((a, b) => b[0] - a[0]);  // position descending

    let fleets = 0;
    let maxTime = 0;
    for (const [pos, spd] of cars) {
        const time = (target - pos) / spd;
        if (time > maxTime) {
            fleets++;
            maxTime = time;
        }
    }
    return fleets;
}

C++

int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int n = position.size();
    vector<pair<int,int>> cars(n);
    for (int i = 0; i < n; i++) cars[i] = {position[i], speed[i]};
    sort(cars.begin(), cars.end(), greater<pair<int,int>>());  // position desc

    int fleets = 0;
    double maxTime = 0.0;
    for (auto& [pos, spd] : cars) {
        double time = (double)(target - pos) / spd;
        if (time > maxTime) {
            fleets++;
            maxTime = time;
        }
    }
    return fleets;
}

Watch out:

1. Using integer division for time loses precision on uneven ratios; always use floating point.
2. Sorting by position ascending (and then iterating forward) needs the logic flipped — easier to sort descending.
3. Equal arrival times should merge: use strict > for "new fleet" condition. Using >= mis-splits.

---

Complexity Analysis

	Time	Space
Simulation	impractical	—
Sort + Scan	O(n log n)	O(n)

Bottleneck: sort. Comparison-based sort is optimal unless you leverage position bounds for a bucket sort.

---

Edge Cases

1. Single car — answer 1 regardless of parameters.
2. All cars same speed — each keeps its own time; fleets = n (no merging).
3. All cars identical except for position — cars behind merge into the one ahead as they catch up; actually since speeds are equal, no one catches up — each is its own fleet.
4. Car starts exactly at target — constraint forbids it, but time would be 0.
5. Very slow car behind a very fast one — slow one always arrives later (not caught up), new fleet.
6. Floating-point equality — use epsilon if needed, but for integer inputs strict > on doubles is reliable here.

---

Related Problems

• LC 735 — Asteroid Collision — Stack-based simulation of collisions; similar "front blocks back" logic.
• LC 1776 — Car Fleet II — Time-of-collision queries; harder and uses a stack.
• LC 496 — Next Greater Element I — Same stack-thinking family.
• LC 901 — Online Stock Span — Monotonic-stack flavor.

---

What Is Expected at Each Level

Junior: Tries simulation. Might get the idea after hint "sort by position."

Mid-level: Sorts descending, computes times, scans tracking maxTime, handles the equal-time merge case.

Senior (L4 target): Produces the clean O(n log n) solution fluently, discusses why strict > is correct for merges, and pivots naturally to LC 1776 as a harder extension — using an explicit stack because arrival times cease to be monotone when cars can decelerate after a collision.