Skip to content
16-Week DSA Roadmap
LeetCode #853MediumProblem 5 of 8

Car Fleet

Cars on a one-lane road can't overtake, so fast cars bunch up behind slow ones. Count how many groups arrive at the finish.

  • Sort, then stack to merge groups
  • Monotonic stack

Before this, know: Sorting an array, What a stack is (push, pop, peek), Time = distance ÷ speed

The problem in plain English

n cars drive along a one-lane road toward the same finish line at mile target. Car i starts at mile position[i] and drives at speed[i] miles per hour. Because it’s one lane, a car can never overtake the car in front. If a faster car catches up with a slower one, it slows down and they drive together, bumper to bumper.

A group of cars driving together is called a fleet. A single car on its own is also a fleet. If a car catches up with a fleet exactly at the finish line, it still counts as part of that fleet. Return how many fleets arrive.

LeetCode’s example: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]. We’ll call the cars A to E, in input order:

012targetAspeed 2Bspeed 4Cspeed 1Dspeed 1Espeed 3
Five cars heading to mile 12. Each car's colour is the fleet it ends up in: A and B arrive together, E catches D, and C drives alone. Answer: 3 fleets.

Rules that matter: all positions are different, every car starts before the target, and there can be up to 100,000 cars.

Before you code: think it through

Two ideas make this problem click.

1. Think in arrival times, not speeds. If nothing were in the way, car i would reach the target after time = (target − position) ÷ speed hours. Car B at mile 8 with speed 4 needs (12 − 8) ÷ 4 = 1 hour. Car A at mile 10 with speed 2 also needs (12 − 10) ÷ 2 = 1 hour.

2. A car behind catches the car ahead if it would arrive at the same time or sooner. B starts behind A but would arrive no later than A, so B must have caught A somewhere on the road (or at the line). Since B can’t pass, they arrive together, at A’s time.

Here is the real motion of LeetCode’s example, worked out minute by minute. Each line is a car’s position over time. When a faster car catches a slower one, its line bends and merges with the slower car’s line:

12012htime →position →ABDEC
Position (up) over time (right). B's line bends onto A's at the finish; E's line catches D's and follows it; C never catches anyone. Three separate lines reach the top: 3 fleets.

Pause and think

target = 10. Car X is at mile 6 with speed 2. Car Y is at mile 2 with speed 4. Does Y catch X before the finish?

Approach 1: Brute force

A car leads its own fleet if there is no car ahead of it that it would catch. So for each car, look at every other car: is there one ahead of it (bigger position) whose time is the same or longer? If yes, our car catches it and is just a follower. If no, our car is the front of a fleet. Count the leaders.

Brute force: check every car ahead

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

012targetA1hB1hC12hD7hE3h
A: 1hB: 1hC: 12hD: 7hE: 3h
variables
checks so far
0
fleets
0
  • Car i
  • Car ahead it catches
  • Leads a fleet
  • Follows someone

Car A alone would take 1h. Is there a car ahead of it that arrives at the same time or later? Then A catches it.

Step 1 / 11

Which line is running?

function carFleet(target, position, speed) {  const n = position.length;  let fleets = 0;  for (let i = 0; i < n; i++) {Running now:     const time = (target - position[i]) / speed[i];    let catchesUp = false;    for (let j = 0; j < n; j++) {      const ahead = position[j] > position[i];      if (ahead && (target - position[j]) / speed[j] >= time) {        catchesUp = true; // car i reaches car j before the target        break;      }    }    if (!catchesUp) fleets++; // nobody to catch: car i leads a fleet  }  return fleets;}

Brute force: check every car ahead

function carFleet(target, position, speed) {  const n = position.length;  let fleets = 0;  for (let i = 0; i < n; i++) {    const time = (target - position[i]) / speed[i];    let catchesUp = false;    for (let j = 0; j < n; j++) {      const ahead = position[j] > position[i];      if (ahead && (target - position[j]) / speed[j] >= time) {        catchesUp = true; // car i reaches car j before the target        break;      }    }    if (!catchesUp) fleets++; // nobody to catch: car i leads a fleet  }  return fleets;}
def car_fleet(target, position, speed):    n = len(position)    fleets = 0    for i in range(n):        time = (target - position[i]) / speed[i]        catches_up = False        for j in range(n):            ahead = position[j] > position[i]            if ahead and (target - position[j]) / speed[j] >= time:                catches_up = True  # car i reaches car j before the target                break        if not catches_up:            fleets += 1  # nobody to catch: car i leads a fleet    return fleets

Why is it slow?

Every car compares itself with every other car. With 5 cars that’s up to 5 × 5 = 25 checks. With 100,000 cars it’s up to 100,000 × 100,000 = 10,000,000,000 checks. That’s O(n²).

The pattern: sort, then stack to merge groups

The brute force re-checks the same cars ahead over and over. If we sort the cars so we process them from the front of the road backwards, then by the time we reach a car, every car ahead of it has already been grouped into fleets. And the only fleet it can possibly catch is the one directly ahead of it.

Pattern

Sort, then stack to merge groups

Template

Use it when: items interact only with their neighbours once put in order, and some of them merge into groups (fleets, overlapping intervals, collisions).

Signal words

  • “fleet”
  • “catch up”
  • “cannot pass”
  • “merge”
  • “how many groups arrive”

Why is a fleet’s arrival time just its front car’s time? Cars behind the front car only catch up to it, they never make it go faster. So the fleet arrives when its front car would have arrived on an empty road. The times on the stack always increase from bottom to top, which makes it a monotonic stack too.

Approach 2: Sort, then a stack of fleets

  1. For every car, compute time = (target − position) ÷ speed. Keep it paired with the position.
  2. Sort the pairs by position, largest first (closest to the target first).
  3. Make an empty stack of arrival times, one per fleet.
  4. For each car in that order: if the stack is empty, or this car’s time is greater than the time on top, push its time: it’s a new fleet. Otherwise it catches the fleet ahead and merges: push nothing.
  5. Return the stack’s size.

Press Play. The road shows every car; each car gets the colour of its fleet as it’s processed, and the stack on the left grows only when a new fleet is born. The tie at the target edge case shows a car that catches up exactly at the line.

Sort, then stack the fleets

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

012targetAspeed 2Bspeed 4Cspeed 1Dspeed 1Espeed 3
stackfleet arrival times
  1. empty
variables
order (front first)
—
this car's time
—
fleet ahead arrives
—
fleets
0
  • Fleet #1
  • Fleet #2
  • Fleet #3
  • Not placed yet

5 cars on a one-lane road heading to mile 12. Nobody can overtake, so a fast car stuck behind a slow one has to slow down.

Step 1 / 9

Which line is running?

Running now: function carFleet(target, position, speed) {  // pair each car's position with the time it needs to reach the target  const cars = position.map((p, i) => [p, (target - p) / speed[i]]);  cars.sort((a, b) => b[0] - a[0]); // closest to the target first  const stack = []; // arrival time of each fleet, front fleet at the bottom  for (const [, time] of cars) {    if (stack.length === 0 || time > stack.at(-1)) {      stack.push(time); // slower than the fleet ahead: a new fleet    }    // otherwise it catches up and joins the fleet ahead  }  return stack.length;}

The code, line by line

Sort, then stack

function carFleet(target, position, speed) {  // pair each car's position with the time it needs to reach the target  const cars = position.map((p, i) => [p, (target - p) / speed[i]]);  cars.sort((a, b) => b[0] - a[0]); // closest to the target first  const stack = []; // arrival time of each fleet, front fleet at the bottom  for (const [, time] of cars) {    if (stack.length === 0 || time > stack.at(-1)) {      stack.push(time); // slower than the fleet ahead: a new fleet    }    // otherwise it catches up and joins the fleet ahead  }  return stack.length;}
def car_fleet(target, position, speed):    # pair each car's position with the time it needs to reach the target    cars = [(p, (target - p) / s) for p, s in zip(position, speed)]    cars.sort(reverse=True)  # closest to the target first    stack = []  # arrival time of each fleet, front fleet at the bottom    for _, time in cars:        if not stack or time > stack[-1]:            stack.append(time)  # slower than the fleet ahead: a new fleet        # otherwise it catches up and joins the fleet ahead    return len(stack)

Lines 1–8 match in both languages; after that JavaScript has a closing } and runs one line ahead.

  • Line 1: define the function. (LeetCode wraps it as var carFleet = function(...), or a method of class Solution in Python.)
  • Line 3: build a list of pairs [position, time]. In JavaScript, map visits each position p with its index i, so speed[i] is the same car’s speed. In Python, zip(position, speed) walks both lists side by side. / gives a decimal in both languages, which is what we want: times like 2.5 hours are real.
  • Line 4: sort by position, biggest first. JavaScript’s sort needs a compare function: b[0] - a[0] puts the larger position first. Python sorts pairs by their first item, and reverse=True makes it largest first.
  • Line 5: the stack holds one arrival time per fleet. The front fleet is at the bottom.
  • Line 6: walk the cars from the front of the road backwards. We only need the time, so we skip the position ([, time] in JS, _, time in Python).
  • Line 7: the decision. stack.at(-1) / stack[-1] is the arrival time of the fleet directly ahead. If our car needs more time, it never catches up.
  • Line 8: push its time: a new fleet, led by this car.
  • Line 10 (JS) / line 9 (Py): the else that isn’t there. A car that would arrive at the same time or earlier merges into the fleet ahead, which keeps the fleet’s (slower) time. Nothing to do.
  • Line 12 (JS) / line 10 (Py): one stack entry per fleet.

Dry run

LeetCode’s example, target = 12. After sorting, the cars come in the order A (10), B (8), D (5), E (3), C (0).

carpositiontime = (12 − pos) ÷ speedtop of stackdecisionstack after
A102 ÷ 2 = 1(empty)new fleet[1]
B84 ÷ 4 = 111 is not > 1: joins A[1]
D57 ÷ 1 = 717 > 1: new fleet[1, 7]
E39 ÷ 3 = 373 is not > 7: joins D[1, 7]
C012 ÷ 1 = 12712 > 7: new fleet[1, 7, 12]
endreturn 3[1, 7, 12]
target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

Row B is the “tie” rule in action: B would arrive at exactly the same time as A, so it catches A at the finish line, and that counts as one fleet.

Complexity

Brute force

Time

O(n²)

Each car checks every other car.

Space

O(1)

Just a counter and a couple of variables.

Sort, then stack

Time

O(n log n)

Sorting costs about n × log₂ n steps (100,000 cars ≈ 1.7 million steps). The loop after it is only n steps.

Space

O(n)

The list of (position, time) pairs, and a stack with up to n fleets.

O(n log n) reads “n log n”: a bit more than straight-line O(n), much less than O(n²). It’s the usual cost of a good sort. log n is explained in the week 3 overview.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Restate the no-overtaking rule and the “catch up at the line counts” rule.
  2. “Convert each car to its arrival time on an empty road.”
  3. “A car only cares about the fleet directly ahead, so sort by position, front first.”
  4. “A car whose time is bigger than the fleet ahead starts a new fleet; otherwise it merges.” Stack of times, answer = its size.
  5. Cost: O(n log n) for the sort, O(n) space. Dry-run the tie.

Likely follow-up questions:

  • “Can you avoid the stack?” Yes: you only ever compare with the top, so a single variable slowestAhead and a counter work too. The stack makes the fleets visible.
  • “When does each fleet arrive?” The values on the stack are exactly those times.
  • “Cars can overtake?” Then nobody merges, and the answer is just n.

Related problems:

  • Daily Temperatures (this week): a monotonic stack without the sort.
  • Merge Intervals (week 12 of the roadmap): the same “sort, then merge with the last group” idea.
  • The week 3 overview has the template.