Car Fleet
Asked at JPMorgan
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| JPMorgan | Medium | View all JPMorgan questions → |
How to Think About It
Cars cannot pass each other, so the only car that matters for a given car is the fleet directly ahead of it.
Compute each car's solo arrival time: (target - position) / speed.
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".
You only need to remember the arrival time of the most recent fleet — a single variable (or a monotonic stack).
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).
What Trips People Up in Real Interviews
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.
Solution Code
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 fleetsFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.