Skip to main content
Talentd

Car Fleet - Solution & Explanation

MediumArrayStackSortingMonotonic Stack12 min readAsked at: Amazon, Microsoft, Goldman Sachs +8
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • 0 < target <= 106
  • 0 <= position[i] < target
  • All the values of position are 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.

This solution uses a struct to store the position and time of each car to reach the target. By sorting cars based on position in descending order, we process them starting from the farthest from the target. We keep track of the `currentTime` indicating the time of the last fleet formed. If a car's time is greater than this, it starts a new fleet, and we update `currentTime` to this car's time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting of cars
Space Complexity: O(n) for storing car times and positions

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Time Calculation

Time Complexity: O(n log n) due to sorting of cars
Space Complexity: O(n) for storing car times and positions

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Time ComparisonO(n log n)O(1)Best general solution. Minimal memory and straightforward logic.
Monotonic Stack of Arrival TimesO(n log n)O(n)Useful when explaining fleet formation using stack or monotonic patterns.

Video Solution

Car Fleet - Leetcode 853 - Python • NeetCode • 345,684 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Car Fleet with our built-in code editor and test cases.

Practice on FleetCode
Previous

Car Fleet II

Next

Count Collisions on a Road