Car Fleet — Solution in Python, Java & C++
Car Fleet solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Nutanix.
Car Fleet is a medium coding problem on arrays, sorting and stack, asked in Nutanix interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Stack, Monotonic Stack
- Asked at: Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n cars head to a destination target miles away. Car i starts at position[i] (all distinct) with speed speed[i]. A faster car that catches up to a slower one slows to match it, forming a fleet. A car that catches a fleet exactly at the target still counts as the same fleet.
Return the number of fleets that arrive.
Example 1
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Example 2
Input: target = 10, position = [3], speed = [3]
Output: 1
Example 3
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Constraints
1 <= position.length == speed.length <= 250 <= position[i] < target <= 1000 (distinct)1 <= speed[i] <= 100
Hints for Car Fleet
Hint 1
Sort by starting position (closest to target first) and compute each car's arrival time.
Hint 2
Scan: a car whose time exceeds the current lead time starts a new fleet.
How to solve Car Fleet
Cars never overtake — a faster car that catches a slower one is stuck behind it forever. So the only thing that decides the answer is arrival time: if a car would reach the target no later than the car ahead of it, it never arrives separately, it merges. Work from the car closest to the target backwards and the whole problem collapses into a single sweep.
Approach
- For each car compute the time it would take alone:
(target - position[i]) / speed[i]. - Sort the cars by starting position, closest to the target first. That is the order they appear on the road, front to back.
- Sweep front to back keeping
lead— the arrival time of the fleet currently ahead. - If the current car's time is greater than
lead, nothing ahead can hold it up, so it starts a new fleet: count it and setleadto its time. - Otherwise it catches the fleet in front and merges —
leadis unchanged, because the fleet still moves at the pace of its slowest car.
Why it works
Because cars cannot pass, a car merges into the fleet ahead exactly when its solo arrival time is no later than that fleet's. Sweeping front to back, lead always holds the arrival time of the slowest car ahead of the current one, and that is precisely the car that would block it. Every time we see a strictly larger time we have found a car nothing ahead can slow down — a new fleet — so the count is exact.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Use floating-point (or cross-multiplied) division for the arrival time. Integer division rounds distinct arrival times together and merges fleets that really do arrive apart.
- A car that catches a fleet exactly at the target counts as the same fleet, so the new-fleet test is a strict
>, not>=. - Sort by position, not by input order — the input is not given along the road.
Reference solution
Python
from typing import List
def carFleet(target: int, position: List[int], speed: List[int]) -> int:
cars = sorted(zip(position, speed), key=lambda c: -c[0])
fleets = 0
lead = -1.0
for p, s in cars:
time = (target - p) / s
if time > lead:
fleets += 1
lead = time
return fleetsJava
public static int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> position[b] - position[a]);
int fleets = 0;
double lead = -1.0;
for (int k = 0; k < n; k++) {
int j = idx[k];
double time = (double) (target - position[j]) / speed[j];
if (time > lead) {
fleets++;
lead = time;
}
}
return fleets;
}C++
int carFleet(int target, vector<int>& position, vector<int>& speed) {
int n = position.size();
vector<pair<int, double>> cars;
for (int i = 0; i < n; i++) {
cars.push_back(make_pair(position[i], (double) (target - position[i]) / speed[i]));
}
sort(cars.begin(), cars.end(), [](const pair<int, double>& a, const pair<int, double>& b) {
return a.first > b.first;
});
int fleets = 0;
double lead = -1.0;
for (int i = 0; i < n; i++) {
if (cars[i].second > lead) {
fleets++;
lead = cars[i].second;
}
}
return fleets;
}JavaScript
var carFleet = function(target, position, speed) {
const cars = position
.map(function(p, i) { return { p: p, time: (target - p) / speed[i] }; })
.sort(function(a, b) { return b.p - a.p; });
let fleets = 0, lead = -1;
for (const c of cars) {
if (c.time > lead) {
fleets++;
lead = c.time;
}
}
return fleets;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms