MediumArrayStackSortingMonotonic StackUpdated Sep 2026

853. Car Fleet

Asked at JPMorgan

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

There is a one-lane road that ends at mile target. You are given two arrays of length n: position[i] is the starting mile of car i, and speed[i] is how fast it drives (miles per hour). Every car drives toward target.

Cars cannot pass each other. If a faster car catches up to a slower car in front of it, it must slow down and drive right behind it. A fleet is one car alone, or a group of cars driving together. The speed of a fleet is the speed of its slowest car. If a car catches a fleet exactly at target, it still counts as part of that fleet.

Return the number of fleets that reach target.

Cars on a one-lane road

road (mile)03581001234target = 12; the cars at 10 and 8 both need 1 hour andmeet at the targetspeed1314201234the car at 3 (speed 3) catches the car at 5 (speed 1),so they become one fleet
Cars cannot pass, so a fast car behind a slow car must slow down and join it as one fleet.

Constraints

  • ●n == position.length == speed.length
  • ●1 <= n <= 10^5
  • ●0 < target <= 10^6
  • ●0 <= position[i] < target
  • ●All values of position are unique
  • ●0 < speed[i] <= 10^6

Examples

Example 1
Inputtarget = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output3
WhyThe car at 10 needs 1 hour and the car at 8 also needs 1 hour, so they meet at the target and form one fleet. The car at 0 needs 12 hours and never catches anyone, so it is a fleet alone. The car at 3 needs 3 hours and catches the slower car at 5 (which needs 7 hours), so those two form one fleet. T
Example 2
Inputtarget = 10, position = [3], speed = [3]
Output1
WhyThere is only one car, so there is exactly one fleet.
Example 3
Inputtarget = 100, position = [0,2,4], speed = [4,2,1]
Output1
WhyThe car at 0 (fast) catches the car at 2, and later that group catches the car at 4. All three end up driving together, so only one fleet arrives.

Asked At

1 companies
CompanyDifficulty
JPMorganMediumView all JPMorgan questions →

How to Think About It

1

Cars cannot pass each other, so the only car that matters for a given car is the fleet directly ahead of it.

2

Compute each car's solo arrival time: (target - position) / speed.

3

Key insight: sort cars by position, closest to the target first. Walk backward: if a car's arrival time is less than or equal to the time of the fleet ahead, it catches that fleet and merges. Otherwise it arrives later and forms a new fleet, which becomes the new "fleet ahead".

4

You only need to remember the arrival time of the most recent fleet — a single variable (or a monotonic stack).

5

Walkthrough: target 12, positions [10,8,0,5,3], speeds [2,4,1,1,3]. Times by position desc: 10 -> 1, 8 -> 1, 5 -> 7, 3 -> 3, 0 -> 12. Fleets: 1 (new), 1 (merge), 7 (new), 3 (merge), 12 (new) -> 3 fleets.

Optimal Approach

Step 1: Pair cars as (position, speed) and sort by position descending.
Step 2: fleets = 0, lead = 0.
Step 3: For each car: t = (target - position) / speed. If t > lead: fleets += 1, lead = t.
Step 4: Return fleets.

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

Sort by position, then scan backward

arrival time, closest first11731201234leadtimes for positions 10, 8, 5, 3, 0 — the first carsets lead = 1arrival time, closest first11731201234leadtime 1 <= lead 1, so merge; time 7 > lead 1, so a newfleet starts and lead becomes 7if t > lead: fleets += 1; lead = ttimes 1, 1, 7, 3, 12 → 3 fleets
Compare each car's solo arrival time with the fleet directly ahead; a smaller-or-equal time means it merges.
ComplexityTime O(n log n)Space O(n)Sorting the cars by position costs O(n log n); the single backward scan is O(n), and the sorted array needs O(n) extra space.

What Trips People Up in Real Interviews

1

Simulating cars step by step. Arrival times make it a single sorted pass.

2

Sorting in the wrong direction. You must start from the car closest to the target.

3

Using >= for a new fleet. A car arriving at exactly the same time as the fleet ahead catches it at the target and joins it.

4

Integer division in C++/Java when computing times — use floating point.

Solution Code

O(n log n) time
def carFleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    fleets = 0
    lead = 0.0
    for p, s in cars:
        t = (target - p) / s
        if t > lead:
            fleets += 1
            lead = t
    return fleets

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Car Fleet problem?

Car Fleet puts cars on a one-lane road heading to a target. A faster car that catches a slower one ahead of it slows down and joins it as a fleet. The task is to count how many fleets arrive. The trick is processing cars from the one closest to the target backward and comparing arrival times.

How do you solve Car Fleet?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Car Fleet?

Car Fleet is asked at JPMorgan. It is a medium difficulty problem.

What are common mistakes on Car Fleet?
  • Simulating cars step by step. Arrival times make it a single sorted pass.
  • Sorting in the wrong direction. You must start from the car closest to the target.
  • Using `>=` for a new fleet. A car arriving at exactly the same time as the fleet ahead catches it at the target and joins it.
  • Integer division in C++/Java when computing times — use floating point.