LeetCode 853: Car Fleet in C++ Using Sorting and a Monotonic Stack

Article Summary

The Car Fleet problem asks us to determine how many separate groups of cars will arrive at the same destination.

Each car begins at a different position and travels at a constant speed. However, the road has only one lane, so a faster car cannot pass a slower car ahead of it. If the faster car catches the slower car before or exactly at the destination, the cars become one fleet.

At first, this may appear to be a movement-simulation problem. We might consider repeatedly updating every car's position and checking when cars meet.

That approach quickly becomes complicated because:

• Cars can catch one another at different times.
• Cars can merge into fleets.
• A fast car must slow down after joining a slower fleet.
• A newly formed fleet may interact with another fleet later.

The central insight is that we do not need to simulate the movement.

Instead, we calculate how long each car would take to reach the destination if it traveled alone. After sorting the cars from closest to farthest from the destination, we compare each car's arrival time with the arrival time of the fleet immediately ahead.

A monotonic stack stores the arrival time of every fleet confirmed so far.

If a car reaches the destination later than the fleet ahead, it cannot catch that fleet and must form a new fleet. Otherwise, it catches the fleet ahead and becomes part of it.

This article develops that idea step by step, explains why sorting is necessary, identifies the stack invariant, proves the algorithm's correctness, and derives the time and space complexity.

Original Problem and Credit

This article is based on the LeetCode problem “853. Car Fleet.”

• Original problem: https://leetcode.com/problems/car-fleet/description/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The original problem statement is summarized and adapted rather than reproduced in full.

Real-World Scenario

Imagine a hypothetical autonomous logistics system that coordinates delivery vehicles traveling through a long, single-lane industrial corridor.

Every vehicle is moving toward the same distribution checkpoint.

For each vehicle, the system knows:

• Its current position in the corridor
• Its constant planned speed
• The position of the destination checkpoint

Because the corridor has only one lane, vehicles are not allowed to pass one another.

A faster vehicle may catch a slower vehicle ahead of it. Once that happens, the faster vehicle must reduce its speed and remain behind the slower vehicle. From that point forward, the two vehicles move together as one convoy.

A single vehicle that never joins another vehicle is also considered a convoy.

The logistics system must determine:

How many separate vehicle convoys will eventually arrive at the destination?

This scenario is hypothetical. It preserves the original computational rules:

• Every vehicle has one starting position.
• Every vehicle has one speed.
• All vehicles move toward the same destination.
• A vehicle cannot pass another vehicle ahead of it.
• Vehicles that meet before or exactly at the destination become one fleet.
• A single vehicle counts as one fleet.
• The required result is the total number of fleets.

Examples

Example 1

Input:
target = 12
position = [10,8,0,5,3]
speed = [2,4,1,1,3]

Output:
3

The cars can be grouped into three fleets:

• The cars starting at positions 10 and 8 form one fleet.
• The cars starting at positions 5 and 3 form another fleet.
• The car starting at position 0 remains by itself.

Therefore, the answer is:

3

Example 2

Input:
target = 10
position = [3]
speed = [3]

Output:
1

There is only one car, so it forms one fleet.

Example 3

Input:
target = 100
position = [0,2,4]
speed = [4,2,1]

Output:
1

The cars behind are fast enough to catch the slower cars ahead before reaching the target.

All three cars eventually become one fleet.

Constraints

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

Mapping to the Original Problem

The surrounding scenario changes, but the input types, movement rules, fleet behavior, and required result remain identical.

Solution Intuition

Start with the Information Given by the Problem

When first reading the problem, we know:

1. Every car moves toward the same target.
2. Every car begins at a different position.
3. Every car has its own constant speed.
4. A car cannot pass another car ahead of it.
5. A faster rear car may catch a slower front car.
6. After catching another car, both cars move together.
7. We only need the final number of fleets.

The difficult part is that a car's original speed may not remain its effective speed.

For example, a fast car may begin with speed 5, catch a car traveling at speed 2, and then be forced to continue at speed 2.

This makes direct simulation appear reasonable.

We might try to update every car's position repeatedly:

new position = old position + speed × time

However, this approach creates many additional questions:

• What time interval should we simulate?
• What happens when multiple cars meet at nearly the same time?
• How do we update the speed of a newly formed fleet?
• How do we handle fleets that later merge with other fleets?
• How do we avoid floating-point simulation errors?

Before simulating movement, we should look for a simpler quantity that summarizes each car's journey.

Comparing Speeds Alone Is Not Enough

A faster rear car does not always catch a slower front car.

The front car may already be extremely close to the target.

For example:

Target: 100

Front car:
Position = 99
Speed = 1

Rear car:
Position = 0
Speed = 2

The rear car is faster, but the front car only needs one unit of time to reach the target.

The rear car needs:

(100 - 0) / 2 = 50

units of time.

The rear car cannot catch the front car before the front car reaches the target.

Therefore, speed alone is not sufficient.

We need to consider both:

• Remaining distance
• Speed

The value that combines them is arrival time.

Convert Movement into Arrival Time

For a car at position p with speed s, the remaining distance is:

target - p

Using the standard relationship:

time = distance / speed

the time required to reach the target is:

time = (target - position) / speed

For example:

target = 12
position = 5
speed = 2

The car's arrival time is:

(12 - 5) / 2 = 3.5

This transformation is the key simplification.

Instead of tracking where every car is at every moment, we represent each car using one number:

The time the car would need to reach the target if it traveled alone.

The problem now becomes an arrival-time comparison problem rather than a continuous movement simulation.

Preserve the Relationship Between Position and Speed

The input stores positions and speeds in two separate vectors:

position[i]
speed[i]

The values at the same index describe the same car.

For example:

position[2] = 5;
speed[2] = 3;

means the same car is:

Position = 5
Speed = 3

We need to sort the cars by position. If we sort only the position vector, the speeds would no longer remain connected to the correct cars.

Therefore, we combine each position and speed into a pair:

vector<pair<int, int>> pv;

Each element stores:

{position, speed}

The pairing is created with:

for (int i = 0; i < static_cast<int>(position.size()); ++i) {
    pv.push_back({position[i], speed[i]});
}

Now every car's position and speed remain together during sorting.

Why the Cars Must Be Sorted by Position

The input order does not necessarily match the physical order of the cars on the road.

Suppose:

target = 12
position = [10,8,0,5,3]

The road order from closest to farthest from the target is:

10, 8, 5, 3, 0

A rear car can only catch the car or fleet directly ahead of it.

It cannot:

• Catch a car behind it
• Pass through the nearest fleet
• Reach a farther fleet without first interacting with the nearest fleet

Therefore, we must process cars according to their physical road order.

We sort them by position in descending order:

sort(pv.rbegin(), pv.rend());

After sorting:

• The first car is closest to the target.
• The second car is directly behind the first.
• Every later car is farther from the target.

This allows us to process the road from front to back.

Begin with Only Two Cars

Before considering all cars, consider only:

A front car or fleet
A rear car

Let:

frontTime = arrival time of the front fleet
rearTime = independent arrival time of the rear car

There are two possible cases.

Case 1: The Rear Car Arrives Earlier or at the Same Time

rearTime <= frontTime

The rear car would reach the target no later than the front fleet if it could move freely.

However, it begins behind the front fleet and cannot pass it.

Therefore, it must catch the front fleet before or exactly at the target.

Once it catches the fleet, it becomes part of that fleet.

The number of fleets does not increase.

For example:

Front fleet arrival time = 7
Rear car arrival time = 3

The rear car would reach the target much earlier by itself, so it must catch the slower fleet ahead.

After joining the fleet, the rear car can no longer arrive in 3 units of time. It must move with the fleet and arrive after 7 units of time.

Case 2: The Rear Car Arrives Later

rearTime > frontTime

The front fleet reaches the target before the rear car could catch it.

Therefore, the rear car cannot join the front fleet.

It forms a new fleet.

For example:

Front fleet arrival time = 7
Rear car arrival time = 10

The front fleet is already at the target after 7 units of time.

The rear car requires 10 units of time, so it cannot catch the front fleet.

Why Equal Arrival Times Form One Fleet

The condition for creating a new fleet is:

time > st.top()

It is strictly greater.

Suppose:

Current car time = 3
Front fleet time = 3

The current car catches the front fleet exactly when both reach the target.

The problem states that cars meeting exactly at the target still count as one fleet.

Therefore:

time == st.top()

must not create a new fleet.

This is why the code does not use:

time >= st.top()

What the Stack Stores

The stack is declared as:

stack<double> st;

Each stack value represents:

The arrival time of one confirmed fleet.

The stack does not store one value for every car.

If several cars merge into the same fleet, only one fleet arrival time remains represented.

For example:

Stack from bottom to top: [1, 7, 12]

This means the processed cars currently form three fleets:

• One fleet reaches the target after 1 unit of time.
• One fleet reaches the target after 7 units of time.
• One fleet reaches the target after 12 units of time.

The top of the stack represents the nearest existing fleet ahead of the next car being processed.

Why Only the Stack Top Matters

Suppose the stack contains:

[1, 7, 12]

The next unprocessed car is behind all three fleets.

The nearest fleet ahead is the fleet represented by:

st.top()

which is:

12

The current car cannot skip that fleet and directly interact with the fleets represented by 7 or 1.

The nearest fleet is physically between the current car and every earlier fleet.

There are only two possibilities.

The Current Car Catches the Nearest Fleet

If:

currentTime <= 12

the current car catches that fleet.

After joining it, the car must travel with the fleet and arrive after 12 units of time.

There is no need to compare the current car with any deeper stack value.

The Current Car Cannot Catch the Nearest Fleet

If:

currentTime > 12

the current car cannot catch even the nearest fleet.

It therefore cannot pass through that fleet to reach another fleet farther ahead.

The current car forms a new fleet.

Again, no deeper stack comparison is necessary.

This is why the algorithm only compares with st.top().

Why This Version Does Not Pop

Some Car Fleet solutions perform the following operations:

1. Push the current arrival time.
2. Compare the last two stack values.
3. Pop the current time if the car joins the fleet ahead.

This implementation uses an equivalent but simpler strategy:

if (st.empty() || time > st.top()) {
    st.push(time);
}

The current arrival time is pushed only when it represents a new fleet.

Suppose:

Front fleet time = 7
Current car time = 3

Because:

3 <= 7

the current car catches the fleet ahead.

Its independent arrival time of 3 is no longer relevant because the merged fleet arrives after 7 units of time.

There is no reason to push 3 and immediately remove it.

The code simply does nothing.

The Monotonic Property

The fleet arrival times are strictly increasing from the bottom of the stack to the top.

For example:

Bottom: 1
        7
Top:    12

A new arrival time is pushed only when:

time > st.top()

Therefore, every newly pushed value is greater than the previous top.

The stack invariant is:

From bottom to top, the stack contains strictly increasing arrival times, with exactly one value for every confirmed fleet.

This makes the structure a monotonic increasing stack.

Unlike some monotonic-stack problems, this implementation does not maintain the order by repeatedly popping values.

Instead, it maintains the order by refusing to push a value when the current car belongs to the fleet already represented by the stack top.

Algorithm

1. Create an empty vector of {position, speed} pairs.
2. For every car:
   1. Combine position[i] and speed[i].
   2. Add the pair to the vector.
3. Sort the pairs by position in descending order.
4. Create an empty stack of fleet arrival times.
5. Process each car from closest to farthest from the target:
   1. Calculate its independent arrival time:

      (target - currentPosition) / currentSpeed
      

   2. If the stack is empty:
      • Push the time because the car forms the first fleet.
   3. Otherwise, compare the current arrival time with the stack top.
   4. If the current time is greater than the stack top:
      • The car cannot catch the fleet ahead.
      • Push the current time as a new fleet.
   5. Otherwise:
      • The car catches the fleet ahead.
      • Do not push another fleet time.
6. Return the number of values in the stack.

Why the Algorithm Works

The correctness of the algorithm follows from the order in which cars are processed and the meaning of the stack.

Invariant

After processing any number of cars in descending position order:

The stack contains exactly one arrival time for every distinct fleet formed by the processed cars. The times are strictly increasing from bottom to top, and the top represents the nearest fleet ahead of the next unprocessed car.

Base Case

Before processing any cars, the stack is empty.

No cars and no fleets have been processed, so the invariant is true.

When the first car is processed, the stack is empty.

Because this is the frontmost car, there is no processed fleet ahead of it. It must form a fleet by itself.

The algorithm pushes its arrival time.

The stack now contains one arrival time for exactly one fleet, so the invariant remains true.

Case 1: The Current Time Is Less Than or Equal to the Stack Top

Suppose:

currentTime <= st.top()

The current car is behind the fleet represented by the stack top.

If the current car traveled freely, it would reach the target before or at the same time as that fleet.

Because it starts behind the fleet and cannot pass it, it must catch the fleet before or exactly at the target.

The current car joins the existing fleet.

No new fleet is created, so the stack should remain unchanged.

The algorithm does not push the current time, preserving the invariant.

Case 2: The Current Time Is Greater Than the Stack Top

Suppose:

currentTime > st.top()

The fleet ahead reaches the target before the current car can catch it.

The current car therefore cannot join the nearest fleet.

Because the nearest fleet lies between the current car and every earlier fleet, the current car cannot join any previously processed fleet.

It must form a new fleet.

The algorithm pushes currentTime.

Because currentTime is greater than the previous stack top, the stack remains strictly increasing.

The invariant is preserved.

Final State

After all cars have been processed, every final fleet is represented by exactly one arrival time in the stack.

Therefore:

st.size()

is exactly the number of car fleets that reach the target.

Complexity Analysis

Let n be the number of cars.

Time Complexity

Creating the position-speed pairs processes each car once:

O(n)

Sorting the n pairs by position requires:

O(n log n)

The final loop processes each sorted car once.

For every car, the algorithm performs:

• One arrival-time calculation
• One stack emptiness check
• At most one top() operation
• At most one push() operation

Each of these operations takes constant time.

The final scan therefore requires:

O(n)

The total running time is:

O(n) + O(n log n) + O(n)

The sorting term dominates, so the final time complexity is:

O(n log n)

Space Complexity

The pv vector stores one position-speed pair for every car:

O(n)

In the worst case, every car forms its own fleet.

The stack may therefore store n arrival times:

O(n)

The remaining variables use constant space.

Therefore, the total auxiliary space complexity is:

O(n)

Although the algorithm uses two structures that may each contain n elements, the result is not reported as O(2n).

Big-O notation ignores constant factors, so:

O(2n) = O(n)

Sorting and Monotonic Increasing Stack

#include <algorithm>
#include <stack>
#include <utility>
#include <vector>

class Solution {
public:
    int carFleet(
        int target,
        std::vector<int>& position,
        std::vector<int>& speed
    ) {
        std::vector<std::pair<int, int>> pv;

        for (
            int i = 0;
            i < static_cast<int>(position.size());
            ++i
        ) {
            pv.push_back({position[i], speed[i]});
        }

        // Process cars from closest to farthest from the target.
        std::sort(pv.rbegin(), pv.rend());

        // Each value represents the arrival time of one fleet.
        std::stack<double> st;

        for (
            const auto& [currentPosition, currentSpeed] : pv
        ) {
            const double time =
                static_cast<double>(
                    target - currentPosition
                ) /
                currentSpeed;

            // A later arrival time means this car cannot catch
            // the nearest fleet ahead, so it forms a new fleet.
            if (st.empty() || time > st.top()) {
                st.push(time);
            }
        }

        return static_cast<int>(st.size());
    }
};

Walkthrough

Consider:

target = 12
position = [10,8,0,5,3]
speed = [2,4,1,1,3]

Step 1: Pair Each Position with Its Speed

The input describes the following cars:

Position 10, speed 2
Position 8, speed 4
Position 0, speed 1
Position 5, speed 1
Position 3, speed 3

The pair vector becomes:

[(10,2), (8,4), (0,1), (5,1), (3,3)]

Step 2: Sort by Position in Descending Order

After:

sort(pv.rbegin(), pv.rend());

the vector becomes:

[(10,2), (8,4), (5,1), (3,3), (0,1)]

This is the physical road order from closest to farthest from the target.

Step 3: Process the Car at Position 10

Position = 10
Speed = 2

Its arrival time is:

(12 - 10) / 2 = 1

The stack is empty, so this car forms the first fleet.

Stack: [1]

Step 4: Process the Car at Position 8

Position = 8
Speed = 4

Its arrival time is:

(12 - 8) / 4 = 1

Compare it with the nearest fleet ahead:

Current time = 1
Fleet time = 1

The new-fleet condition is:

1 > 1

This is false.

The car at position 8 catches the front car exactly at the target.

They count as one fleet.

The stack remains:

[1]

Step 5: Process the Car at Position 5

Position = 5
Speed = 1

Its arrival time is:

(12 - 5) / 1 = 7

Compare:

Current time = 7
Fleet time = 1

The condition becomes:

7 > 1

This is true.

The fleet ahead reaches the target after 1 unit of time, while the current car requires 7.

The current car cannot catch that fleet, so it forms a new fleet.

Push 7:

Stack: [1, 7]

Step 6: Process the Car at Position 3

Position = 3
Speed = 3

Its arrival time is:

(12 - 3) / 3 = 3

Compare:

Current time = 3
Nearest fleet time = 7

The condition becomes:

3 > 7

This is false.

The car at position 3 would arrive earlier if it traveled freely, so it catches the fleet at position 5.

After joining that fleet, it must arrive after 7 units of time.

No new time is pushed.

The stack remains:

[1, 7]

Step 7: Process the Car at Position 0

Position = 0
Speed = 1

Its arrival time is:

(12 - 0) / 1 = 12

Compare:

Current time = 12
Nearest fleet time = 7

The condition becomes:

12 > 7

This is true.

The current car cannot catch the fleet ahead, so it forms another fleet.

Push 12:

Stack: [1, 7, 12]

Final Result

The stack contains:

[1, 7, 12]

Each value represents one fleet.

Therefore:

Number of fleets = 3

The function returns:

3

Stack Trace Table

Understanding the Important Lines

Creating the Pair Vector

vector<pair<int, int>> pv;

This creates a vector whose elements are pairs of integers.

Each pair stores:

{position, speed}

Combining the Two Input Vectors

for (int i = 0; i < static_cast<int>(position.size()); ++i) {
    pv.push_back({position[i], speed[i]});
}

The loop visits every car.

For each index i, it combines the corresponding position and speed into one pair.

Sorting from Closest to Farthest

sort(pv.rbegin(), pv.rend());

rbegin() and rend() are reverse iterators.

Using them with sort() arranges the pairs in descending order.

Because the first value in each pair is the car's position, the car with the greatest position is processed first.

Creating the Fleet Stack

stack<double> st;

The stack stores one arrival time for every confirmed fleet.

The type is double because arrival times may contain fractional values.

Reading Each Pair

for (const auto& [currentPosition, currentSpeed] : pv)

This is a C++17 structured binding.

For each pair:

• currentPosition receives the first value.
• currentSpeed receives the second value.

The & avoids copying the pair.

The const prevents the loop from modifying the original pair.

Calculating Arrival Time

double time =
    static_cast<double>(target - currentPosition) /
    currentSpeed;

The remaining distance is:

target - currentPosition

Dividing the remaining distance by the speed gives the arrival time.

The static_cast<double> ensures that C++ performs floating-point division.

Detecting a New Fleet

if (st.empty() || time > st.top()) {
    st.push(time);
}

If the stack is empty, the current car forms the first fleet.

If the current time is greater than the nearest fleet's time, the current car cannot catch that fleet and forms a new one.

Otherwise, the car catches the fleet ahead, so no new stack value is needed.

Returning the Answer

return static_cast<int>(st.size());

Each stack value represents one fleet.

The number of stack values is therefore the final fleet count.

Common Mistakes

Sorting in Ascending Order

The following code processes the farthest car first:

sort(pv.begin(), pv.end());

At that point, the final behavior of the cars ahead has not yet been determined.

The cars should be processed from closest to farthest:

sort(pv.rbegin(), pv.rend());

Sorting Positions Without Their Speeds

Sorting only the position vector breaks the relationship between:

position[i]

and:

speed[i]

The values must be combined before sorting.

Comparing Only Car Speeds

A faster car does not always catch a slower car before the target.

The front car may be too close to the destination.

The correct comparison uses arrival times:

(target - position) / speed

Reversing the New-Fleet Condition

The incorrect condition is:

if (st.empty() || st.top() > time)

If the stack top is greater than the current time, the current car is fast enough to catch the fleet ahead.

That should not create a new fleet.

The correct condition is:

if (st.empty() || time > st.top())

Using Integer Division

The following expression may lose the fractional part:

double time = (target - currentPosition) / currentSpeed;

For example:

9 / 2 = 4

when both operands are integers.

Use:

double time =
    static_cast<double>(target - currentPosition) /
    currentSpeed;

to produce:

9.0 / 2 = 4.5

Treating Equal Arrival Times as Separate Fleets

The following condition is incorrect:

time >= st.top()

When the arrival times are equal, the cars meet exactly at the target and count as one fleet.

The correct condition is:

time > st.top()

Calling top() on an Empty Stack

The code must verify that the stack is not empty before accessing st.top().

The supplied condition is safe:

if (st.empty() || time > st.top())

C++ uses short-circuit evaluation. If st.empty() is true, st.top() is not evaluated.

Assuming Every Car Must Be Pushed

The stack represents fleets, not individual cars.

When a car catches the fleet ahead, its independent arrival time should not be stored.

The fleet ahead already represents the merged group.

Replacing the Fleet Time with the Faster Car's Time

Suppose:

Front fleet time = 7
Rear car time = 3

After catching the fleet, the rear car cannot continue at its original pace and arrive in 3 units of time.

It must slow down and arrive with the fleet after 7 units of time.

Therefore, the stack keeps 7.

Comparing with Every Fleet

Only the nearest fleet ahead matters.

A car cannot pass through that fleet to interact with a farther fleet.

The stack top represents this nearest fleet, so a single comparison is sufficient.

Assuming a Stack Must Always Pop

Many monotonic-stack algorithms use repeated pop() operations, but popping is not required in every monotonic-stack implementation.

This solution maintains monotonic order by pushing only when a new arrival time is greater than the existing top.

A merging car is simply not pushed.

Could the Stack Be Replaced?

Yes.

This implementation only uses:

st.top()

and:

st.size()

It never needs to inspect older fleet times.

Therefore, the stack can be optimized into:

double previousFleetTime;
int fleetCount;

However, the stack version has an educational advantage:

• Every stack entry visibly represents one fleet.
• The final stack size directly gives the answer.
• The monotonic relationship between fleet arrival times is easy to inspect.
• It connects the problem to the stack and monotonic-stack pattern.

The stack solution is therefore a clear and appropriate way to learn the problem, even though a constant-state variation also exists.

Key Takeaways

• Do not simulate every car's movement when a simpler summary value is available.
• Arrival time combines both remaining distance and speed.
• Cars must be processed from closest to farthest from the target.
• A rear car joins the fleet ahead when its independent arrival time is less than or equal to that fleet's arrival time.
• A rear car forms a new fleet only when its arrival time is strictly greater.
• The stack stores one arrival time per confirmed fleet, not one time per car.
• The stack remains strictly increasing from bottom to top.
• Only the nearest fleet ahead matters because cars cannot pass.
• Sorting determines the O(n log n) time complexity.
• The pair vector and fleet stack require O(n) auxiliary space.

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.