Car Fleet solution and explanation
Google
9 more videos on this problem
Car Fleet - Leetcode 853 - PythonNeetCode · 16:10 · 345K views
LeetCode 853. Car Fleet | Medium | Algorithm Explained | C++Cherry Coding [IIT-G] · 14:21 · 9K views
Leetcode 853 : Car FleetHellgeek Arena · 12:48 · 7K views
Car Fleet | LeetCode 853 (Medium)Destination FAANG · 19:39 · 6K views
Car Fleet LeetCode 853 - Intuitive Guide + CodeCodingNinja · 11:40 · 5K views
853. Car Fleet || NEETCODE 150TechWithSaumya · 15:56 · 4K views
LeetCode | 853. Car Fleet | Monotonic Stack | SortingCompl3x · 20:25 · 2K views
Coding Interview Problem - Car FleetKnapsack · 14:39 · 1K views
Car Fleet | Python Solution | LeetCode 853Сурен Хоренян · 18:09 · 913 views
853. Car Fleet, LeetCode, Javabaobaollf · 11:52 · 811 views
The problem
There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.
You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.
A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.
A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.
If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.
Return the number of car fleets that will arrive at the destination.
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
- The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at
target. - The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
- The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches
target.
Example 2:
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation:
There is only one car, hence there is only one fleet.Example 3:
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
- The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
- Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches
target.
Constraints:
n == position.length == speed.length1 <= n <= 1050 < target <= 1060 <= position[i] < target- All the values of
positionare unique. 0 < speed[i] <= 106
Approach overview
Problem Overview: You are given the position and speed of multiple cars driving toward a target. A faster car cannot pass a slower one ahead of it; instead, it joins that car and forms a fleet that travels at the slower speed. The task is to compute how many distinct fleets will arrive at the target.
Approach 1: Sorting and Time Calculation (O(n log n) time, O(1) space)
The key idea is to process cars from closest to the target to farthest. First, pair each car's position with its speed and sort the cars by position in descending order using sorting. For each car, compute the time needed to reach the target using (target - position) / speed. As you iterate through the sorted list, track the maximum arrival time seen so far. If the current car's time is greater than that maximum, it cannot catch the fleet ahead and forms a new fleet. Otherwise, it merges into the fleet in front.
This works because a car behind can only interact with cars ahead of it. Once a slower fleet forms, any faster car behind it will eventually slow down and join it. By scanning from right to left (closest to farthest), you only need to compare arrival times, which avoids simulating movement.
Approach 2: Monotonic Stack of Arrival Times (O(n log n) time, O(n) space)
This variation uses the same sorting step but explicitly models fleets using a stack. After sorting cars by position descending, compute the arrival time for each car and push it onto a stack. If the new time is less than or equal to the time on top of the stack, it means the car catches the fleet ahead, so you discard it instead of creating a new entry. The stack therefore stays monotonic increasing in arrival time, which is a classic monotonic stack pattern.
The number of elements left in the stack equals the number of fleets. Conceptually, each stack entry represents the final arrival time of a fleet that cannot be caught by any car behind it.
Recommended for interviews: The sorting + time comparison approach is what most interviewers expect. It shows you can reduce a simulation problem to a mathematical observation about arrival times. Mentioning the monotonic stack interpretation demonstrates deeper understanding, especially when discussing patterns involving arrays and ordered traversal.
Approach 1: Sorting and Time Calculation
To solve the Car Fleet problem, we can calculate the time it takes for each car to reach the target. By sorting cars based on their starting positions and calculating their respective arrival times, we can determine when fleets are formed. Cars that catch up to a fleet at the target will become part of that fleet.
def carFleet(target, position, speed):
cars = sorted(zip(position, speed), reverse=True)
times = [(target - p) / s for p, s in cars]
fleets = 0
currentTime = 0
for time in times:
if time > currentTime:
currentTime = time
fleets += 1
return fleets
# Example usage:
target = 12
position = [10, 8, 0, 5, 3]
speed = [2, 4, 1, 1, 3]
print(carFleet(target, position, speed)) # Output: 3import java.util.*;
class CarFleet {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
double[][] cars = new double[n][2];
for (int i = 0; i < n; i++) {
cars[i][0] = position[i];
cars[i][1] = (double)(target - position[i]) / speed[i];
}
Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
int fleets = 0;
double currentTime = 0;
for (int i = 0; i < n; i++) {
if (cars[i][1] > currentTime) {
currentTime = cars[i][1];
fleets++;
}
}
return fleets;
}
public static void main(String[] args) {
CarFleet cf = new CarFleet();
int target = 12;
int[] position = {10, 8, 0, 5, 3};
int[] speed = {2, 4, 1, 1, 3};
System.out.println(cf.carFleet(target, position, speed)); // Output: 3
}
}#include <vector>
#include <algorithm>
class CarFleet {
public:
int carFleet(int target, std::vector<int>& position, std::vector<int>& speed) {
int n = position.size();
std::vector<std::pair<int, double>> cars;
for (int i = 0; i < n; i++) {
cars.emplace_back(position[i], (double)(target - position[i]) / speed[i]);
}
std::sort(cars.begin(), cars.end(), std::greater<>());
int fleets = 0;
double currentTime = 0;
for (const auto& car : cars) {
if (car.second > currentTime) {
currentTime = car.second;
fleets++;
}
}
return fleets;
}
};
int main() {
CarFleet cf;
std::vector<int> position = {10, 8, 0, 5, 3};
std::vector<int> speed = {2, 4, 1, 1, 3};
int target = 12;
int result = cf.carFleet(target, position, speed);
std::cout << result << std::endl; // Output: 3
return 0;
}function carFleet(target, position, speed) {
let cars = position.map((pos, i) => [pos, (target - pos) / speed[i]]);
cars.sort((a, b) => b[0] - a[0]);
let fleets = 0, currentTime = 0;
for (const [pos, time] of cars) {
if (time > currentTime) {
currentTime = time;
fleets++;
}
}
return fleets;
}
// Example usage:
const target = 12;
const position = [10, 8, 0, 5, 3];
const speed = [2, 4, 1, 1, 3];
console.log(carFleet(target, position, speed)); // Output: 3#include <stdio.h>
#include <stdlib.h>
typedef struct {
int position;
double time;
} Car;
int compare(const void* a, const void* b) {
Car* car1 = (Car*)a;
Car* car2 = (Car*)b;
return car2->position - car1->position;
}
int carFleet(int target, int* position, int* speed, int size) {
Car* cars = (Car*)malloc(size * sizeof(Car));
for (int i = 0; i < size; i++) {
cars[i].position = position[i];
cars[i].time = (double)(target - position[i]) / speed[i];
}
qsort(cars, size, sizeof(Car), compare);
int fleets = 0;
double currentTime = 0;
for (int i = 0; i < size; i++) {
if (cars[i].time > currentTime) {
currentTime = cars[i].time;
fleets++;
}
}
free(cars);
return fleets;
}
int main() {
int target = 12;
int position[] = {10, 8, 0, 5, 3};
int speed[] = {2, 4, 1, 1, 3};
int size = 5;
printf("%d\n", carFleet(target, position, speed, size)); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
class CarFleet {
public int CarFleet(int target, int[] position, int[] speed) {
var cars = position.Zip(speed, (p, s) => new { Position = p, Time = (double)(target - p) / s })
.OrderByDescending(car => car.Position)
.ToList();
int fleets = 0;
double currentTime = 0;
foreach (var car in cars) {
if (car.Time > currentTime) {
currentTime = car.Time;
fleets++;
}
}
return fleets;
}
static void Main(string[] args) {
var cf = new CarFleet();
int target = 12;
int[] position = new[] { 10, 8, 0, 5, 3 };
int[] speed = new[] { 2, 4, 1, 1, 3 };
Console.WriteLine(cf.CarFleet(target, position, speed)); // Output: 3
}
}The Python solution makes use of zip to pair positions and speeds, allowing for easier sorting and calculation of times. We iterate through the list of times to determine the number of car fleets, checking if the time is greater than `currentTime` to form a new fleet.
Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) for the creation of times list
Approach 2: Default Approach
function carFleet(target: number, position: number[], speed: number[]): number {
const n = position.length;
const idx = Array(n)
.fill(0)
.map((_, i) => i)
.sort((i, j) => position[j] - position[i]);
let ans = 0;
let pre = 0;
for (const i of idx) {
const t = (target - position[i]) / speed[i];
if (t > pre) {
++ans;
pre = t;
}
}
return ans;
}func carFleet(target int, position []int, speed []int) (ans int) {
n := len(position)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return position[idx[j]] < position[idx[i]] })
var pre float64
for _, i := range idx {
t := float64(target-position[i]) / float64(speed[i])
if t > pre {
ans++
pre = t
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Time Calculation | Time Complexity: O(n log n) due to sorting |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Time Comparison | O(n log n) | O(1) | Best general solution. Minimal memory and straightforward logic. |
| Monotonic Stack of Arrival Times | O(n log n) | O(n) | Useful when explaining fleet formation using stack or monotonic patterns. |
Frequently asked questions
Is Car Fleet easy or hard?
Car Fleet is rated Medium difficulty on LeetCode. The implementation is short, but the challenge is recognizing that cars should be processed from closest to farthest and that arrival times determine fleet formation.
Car Fleet Python/Java solution
In both Python and Java, the typical implementation pairs position and speed, sorts cars by position descending, computes arrival time using (target - position) / speed, and counts fleets while scanning the list. The logic is identical across languages and runs in O(n log n) time.
How to solve Car Fleet in O(n)?
An O(n) solution is not possible in the general case because the cars must be processed in order of position relative to the target. Without sorting, determining which cars interact becomes ambiguous. With sorted input, the fleet counting step itself is O(n).
What is the best approach for Car Fleet?
The standard solution sorts cars by position in descending order and computes each car's arrival time at the target. While iterating, track the maximum time seen so far. If a car's time is greater than the previous maximum, it forms a new fleet; otherwise it joins the fleet ahead. This runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Car Fleet asked at Google/Amazon/Meta?
Car Fleet is a common medium-level interview problem and appears frequently in preparation lists for companies like Amazon, Google, and Meta. It tests sorting, greedy reasoning, and recognizing monotonic patterns rather than complex data structures.
What data structure is used in Car Fleet?
Most implementations use simple arrays and sorting. Some explanations also use a stack to maintain a monotonic sequence of fleet arrival times. The stack is not strictly required but helps illustrate how fleets merge.
What is the time complexity of Car Fleet?
The optimal solution runs in O(n log n) time because the cars must be sorted by position. After sorting, a single pass calculates arrival times and counts fleets in O(n). Space complexity is O(1) if you track only the current maximum time, or O(n) if using an explicit stack.