853. Car Fleet (Medium)

Problem

There are n cars driving to the same target. The i-th car is at position[i] with speed speed[i]. A faster car behind a slower one can never pass; it slows down to the slower car’s speed and they become a fleet. A fleet is a non-empty set of cars driving at the same position with the same speed. A car that catches up to a fleet at the exact target also counts as merging.

Return the number of fleets that arrive at target.

Example

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

LeetCode 853 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, step-wise simulation

Simulate every time step, updating positions and collapsing cars that meet.

Python

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    # Fragile, slow, and fiddly with floating point. Included for contrast.
    cars = sorted(zip(position, speed))
    # ... step positions, merge when adjacent positions equalize, etc.
    # In practice this is buggy; don't do it.
    raise NotImplementedError("Simulation is not recommended for this problem.")

TypeScript

function carFleet(target: number, position: number[], speed: number[]): number {
    // Fragile, slow, and fiddly with floating point. Included for contrast.
    // In practice this is buggy; don't do it.
    throw new Error('Simulation is not recommended for this problem.');
}

Swift

final class Solution {
    func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
        var times = zip(position, speed).map { (position: $0.0, time: Double(target - $0.0) / Double($0.1)) }.sorted { $0.position > $1.position }.map(\.time)
        var index = 1
        while index < times.count {
            if times[index] <= times[index - 1] { times.remove(at: index) } else { index += 1 }
        }
        return times.count
    }
}

Where the time goes

Variables: n = len(position), T = simulation time horizon.

Line	Per-call cost	Times executed	Contribution
sort + simulate	$O(n)$ per step	T steps	$O(n · T)$ ← dominates

T is unbounded in general and may involve floating-point precision issues.

Complexity

• Time: Hard to bound cleanly; effectively $O(n · T)$ where T is the simulation horizon.
• Space: $O(n)$.

Don’t actually simulate, it’s imprecise and slow.

Approach 2: Sort by position descending; compute arrival times

Sort cars by their starting position, nearest-to-target first. Compute each car’s time to reach the target (assuming free travel). A new fleet forms whenever a car arrives strictly later than the fleet ahead of it; otherwise it merges.

Python

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    cars = sorted(zip(position, speed), reverse=True)  # L1: O(n log n) sort descending
    fleets = 0                                          # L2: O(1)
    last_arrival = 0.0                                  # L3: O(1) arrival of fleet ahead
    for pos, spd in cars:                               # L4: n iterations
        arrival = (target - pos) / spd                  # L5: O(1) time to target
        if arrival > last_arrival:                      # L6: O(1) fleet check
            fleets += 1                                 # L7: O(1) new fleet
            last_arrival = arrival                      # L8: O(1) update
    return fleets                                       # L9: O(1)

TypeScript

function carFleet(target: number, position: number[], speed: number[]): number {
    const cars = position.map((p, i) => [p, speed[i]] as [number, number]);
    cars.sort((a, b) => b[0] - a[0]);                  // L1: O(n log n) sort descending
    let fleets = 0;                                     // L2: O(1)
    let lastArrival = 0;                                // L3: O(1) arrival of fleet ahead
    for (const [pos, spd] of cars) {                    // L4: n iterations
        const arrival = (target - pos) / spd;           // L5: O(1) time to target
        if (arrival > lastArrival) {                    // L6: O(1) fleet check
            fleets++;                                   // L7: O(1) new fleet
            lastArrival = arrival;                      // L8: O(1) update
        }
    }
    return fleets;                                      // L9: O(1)
}

Swift

final class Solution {
    func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
        let cars = zip(position, speed).map { (position: $0.0, time: Double(target - $0.0) / Double($0.1)) }.sorted { $0.position > $1.position }
        var fleets = 0
        var slowestAhead = 0.0
        for car in cars where car.time > slowestAhead { fleets += 1; slowestAhead = car.time }
        return fleets
    }
}

Where the time goes, line by line

Variables: n = len(position).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L4-L8 (linear scan)	$O(1)$	n	$O(n)$

The sort dominates; the scan is linear.

Complexity

• Time: $O(n log n)$, driven by L1 (sorting by position). Sorting dominates.
• Space: $O(n)$ for the sort.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Sort + monotonic stack of arrival times (equivalent, stack-explicit)

Same ordering, but use a stack of arrival times to make the “merge behind a slower car” more visual: push the car’s arrival time; skip pushing if the stack top (car ahead) arrives later or equal (faster cars behind catch up and merge).

Python

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    cars = sorted(zip(position, speed), reverse=True)   # L1: O(n log n) sort
    stack = []                                           # L2: O(1)
    for pos, spd in cars:                                # L3: n iterations
        t = (target - pos) / spd                         # L4: O(1) arrival time
        if not stack or t > stack[-1]:                   # L5: O(1) check vs fleet ahead
            stack.append(t)                              # L6: O(1) push new fleet
        # otherwise: catches up to the fleet ahead, merged
    return len(stack)                                    # L7: O(1)

TypeScript

function carFleet(target: number, position: number[], speed: number[]): number {
    const cars = position.map((p, i) => [p, speed[i]] as [number, number]);
    cars.sort((a, b) => b[0] - a[0]);                   // L1: O(n log n) sort
    const stack: number[] = [];                          // L2: O(1)
    for (const [pos, spd] of cars) {                     // L3: n iterations
        const t = (target - pos) / spd;                  // L4: O(1) arrival time
        if (!stack.length || t > stack[stack.length - 1])
            stack.push(t);                               // L5-L6: O(1) push new fleet
        // otherwise: catches up to the fleet ahead, merged
    }
    return stack.length;                                 // L7: O(1)
}

Swift

final class Solution {
    func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
        let cars = zip(position, speed).map { (position: $0.0, time: Double(target - $0.0) / Double($0.1)) }.sorted { $0.position > $1.position }
        var stack: [Double] = []
        for car in cars {
            if let ahead = stack.last, car.time <= ahead { continue }
            stack.append(car.time)
        }
        return stack.count
    }
}

Where the time goes, line by line

Variables: n = len(position).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L3-L6 (scan + stack ops)	$O(1)$	n	$O(n)$
L7 (len)	$O(1)$	1	$O(1)$

Same cost structure as Approach 2; the stack just makes the fleet grouping explicit.

Complexity

• Time: $O(n log n)$, driven by L1 (sorting by position).
• Space: $O(n)$ for the stack.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Time-step simulation	$O(n · T)$	$O(n)$
Sort + arrival times	$O(n log n)$	$O(n)$
Sort + monotonic stack	$O(n log n)$	$O(n)$

The insight: fleets are determined by arrival times in order of starting position, no need to simulate. A slower car ahead caps everyone behind it.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_car_fleet.py and run.
# Uses the canonical implementation (Approach 3: sort + monotonic stack).

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    cars = sorted(zip(position, speed), reverse=True)
    stack = []
    for pos, spd in cars:
        t = (target - pos) / spd
        if not stack or t > stack[-1]:
            stack.append(t)
    return len(stack)

def _run_tests():
    assert car_fleet(12, [10,8,0,5,3], [2,4,1,1,3]) == 3
    assert car_fleet(10, [3], [3]) == 1
    assert car_fleet(100, [0,2,4], [4,2,1]) == 1  # all merge
    assert car_fleet(10, [6,8], [3,2]) == 2       # car at 8 arrives faster, 2 fleets
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function carFleet(target: number, position: number[], speed: number[]): number {
    const cars = position.map((p, i) => [p, speed[i]] as [number, number]);
    cars.sort((a, b) => b[0] - a[0]);
    const stack: number[] = [];
    for (const [pos, spd] of cars) {
        const t = (target - pos) / spd;
        if (!stack.length || t > stack[stack.length - 1]) stack.push(t);
    }
    return stack.length;
}

console.assert(carFleet(12, [10,8,0,5,3], [2,4,1,1,3]) === 3);
console.assert(carFleet(10, [3], [3]) === 1);
console.assert(carFleet(100, [0,2,4], [4,2,1]) === 1);
console.assert(carFleet(10, [6,8], [3,2]) === 2);
console.log('all tests pass');

Related data structures

• Arrays, (position, speed) pairs; sort + pass
• Stacks, visualization of fleet merges

Related concepts

• Monotonic Stack, the ordered stack pattern for nearest greater, nearest smaller, and spans.
• Sorting as Preprocessing, the order first tactic that exposes adjacency, sweep boundaries, and duplicate control.