LeetCode · #853

Car Fleet Solution

Given n cars heading toward a target, determine how many car fleets will arrive.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #853

🏗️

Pattern

Sort + Stack — arrival time comparison

There are n cars going to the same destination target miles away. Each car i starts at position[i] with speed speed[i]. A car can never pass another — if it catches up, they form a fleet and travel at the slower car's speed. Return the number of fleets arriving at the target.

Example

 Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3 // Car at 10 (ETA 1.0) and car at 8 (ETA 1.0) → fleet // Car at 5 (ETA 7.0) and car at 3 (ETA 3.0) → 3 catches 5, fleet at ETA 7.0 // Car at 0 (ETA 12.0) → alone // 3 fleets total 

Constraints

 • n == position.length == speed.length • 1 ≤ n ≤ 10⁵ • 0 < target ≤ 10⁶ • All positions are unique 

Section Two · Approach 1

Brute Force — Simulation

Simulate the cars advancing in tiny time steps, merging fleets when a car catches the one ahead. Too slow for large inputs and requires floating-point precision handling.

Problem: Simulation is complex and slow. The key insight: a car's arrival time is (target − position) / speed. Sort by position and compare arrival times — if a behind car arrives sooner or equal, it joins the fleet ahead.

Section Three · Approach 2

Sort + Stack — O(n log n)

Sort cars by position (closest to target first). Process them in order. Each car's arrival time = (target − position) / speed. If a car's ETA is ≤ the car ahead (on the stack), it merges into that fleet. Otherwise, it forms a new fleet.

💡 Mental model: Imagine watching cars from the finish line. The car closest to you arrives first (or determines the fleet speed). A car behind it that would arrive sooner can't pass — it gets stuck behind and joins the same fleet. Only when a car behind has a later arrival time does it form a new, independent fleet.

Algorithm

Step 1: Pair (position, speed), sort by position descending (closest to target first).
Step 2: For each car, compute ETA = (target − position) / speed.
Step 3: If ETA > stack top → new fleet → push ETA.
Step 4: If ETA ≤ stack top → merges into fleet ahead → skip (don't push).
Step 5: Stack size = number of fleets.

🎯 Key insight:

We only need to compare adjacent cars (sorted by position). A car behind that arrives sooner gets absorbed.
A car behind that arrives later cannot catch the fleet ahead — it starts a new fleet.
The stack naturally tracks fleet arrival times.

Section Four · Trace

Visual Walkthrough

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

Sort by position desc, compare ETAs

Answer: Stack size = 3 fleets.

Section Five · Implementation

Code — Java & Python

Java — Sort + Stack

 import java.util.*;
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
int[][] cars = new int[n][2];
for (int i = 0; i < n; i++) cars[i] = new int[]{position[i], speed[i]};
Arrays.sort(cars, (a, b) -> b[0] - a[0]); // sort by position desc Stack<Double> stack = new Stack<>();
for (int[] car : cars) {
double eta = (double)(target - car[0]) / car[1];
if (stack.isEmpty() || eta > stack.peek())
                stack.push(eta); // new fleet // else: merges into fleet ahead — don't push
}
return stack.size();
    }
}

Python — Sort + Stack

 class Solution:
def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        stack = []
for pos, spd in cars:
            eta = (target - pos) / spd
if not stack or eta > stack[-1]:
                stack.append(eta) # new fleet return len(stack)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sort + Stack ← optimal	O(n log n)	O(n)	Sort dominates. Stack pass is O(n).

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single car	`n=1`	One car → 1 fleet.
All same speed	`spd=[2,2,2]`	Nobody catches anyone → n fleets (if sorted differently).
All merge	Closest car slowest	Everyone catches up → 1 fleet.
Same ETA	Two cars with equal ETA	They meet exactly at target → same fleet. Use ≤ not <.

⚠ Common Mistake: Sorting by position ascending instead of descending. We must process the car closest to the target first — it's the "blocker." Cars behind it can merge into it, but never pass. Processing from farthest-first would miss fleet merges.

← Back to Stack problems

LearningTree

LC 853 · Car Fleet — Solution & Explanation | DSA Guide