Car Fleet

LeetCode 853: Car Fleet Solution & Explanation

Problem Overview

TL;DR: Sort cars from closest to farthest from the target, compute each car’s arrival time, and use a monotonic stack of fleet arrival times to count only arrival times strictly greater than the fleet ahead.

In LeetCode 853: Car Fleet, every car travels toward the same destination and cannot pass another car. When a faster car catches a slower car ahead, both continue as one fleet at the slower fleet speed. The task is to determine how many separate fleets reach target.

The LeetCode 853 Solution uses sorting and a monotonic arrival-time structure. Cars are processed from front to back, allowing each car to be compared only with the fleet immediately ahead of it. This is a popular interview question because it tests sorting, greedy reasoning, and monotonic stack behavior.

Brute Force Approach for Car Fleet

A direct approach is to simulate the movement of every car over time:

1. Track each car’s current position and speed.
2. Advance all cars by a small time interval.
3. Detect when a car reaches or catches the car ahead.
4. Merge caught cars into the same fleet.
5. Continue until all cars reach the destination.

Another less simulation-heavy brute force method repeatedly compares every car with cars ahead of it:

1. Sort cars by position.
2. For every car, determine whether it catches the nearest fleet ahead.
3. If it catches that fleet, merge it.
4. Otherwise, create a new fleet.
5. Repeat comparisons as fleet relationships change.

A simplified pseudo-code version is:

sort cars by position from closest to farthest

fleets = empty list

for each car from front to back:
    currentFleet = car

    for each fleet already created:
        if currentFleet catches that fleet:
            merge currentFleet with fleet
        else:
            stop checking

    if currentFleet remains separate:
        add currentFleet to fleets

return number of fleets

If each car may compare against many existing fleets, the worst-case time complexity is:

O(n^2)

With up to 10^5 cars, quadratic work can require approximately 10^10 comparisons, which is far beyond practical limits and can result in Time Limit Exceeded. Continuous movement simulation is also unsuitable because it introduces unnecessary time-step management and floating-point concerns.

Algorithm Strategy: Stack Patterns

1. Pair each car’s position with its speed.
2. Sort all cars by position in descending order, so the closest car to the target is processed first.
3. For each car, calculate its time to reach the target independently.
4. Maintain the arrival time of every fleet that remains a distinct boundary.
5. Compare the current car’s arrival time with the last fleet arrival time:
   • If it is less than or equal to the last time, the car merges into that fleet.
   • If it is greater, the car cannot catch the fleet ahead and starts a new fleet.
6. Return the number of stored fleet arrival times.

The stack-like structure never needs to remove an existing fleet in this problem. A current car either joins the latest fleet or is pushed as a new fleet boundary.

Execution Flow

1. Sort by position

   • Cars are ordered from largest position to smallest position.
   • This means the scan direction is from the target backward.

2. Process the first car

   • The frontmost car always creates the first fleet.
   • Its arrival time becomes the latest fleet arrival time.

3. Compute the current arrival time

   • For each remaining car, calculate:
     textCopy

     (target - position) / speed

4. Compare with the fleet ahead

   • If the current arrival time is smaller than or equal to the latest fleet arrival time, the current car catches that fleet.
   • No new stack entry is created.

5. Create a new fleet when necessary

   • If the current arrival time is strictly greater, the car arrives later and cannot catch the fleet ahead.
   • Increment the fleet count and store this new arrival time.

6. Finish the scan

   • Every stack entry represents one distinct fleet.
   • Return the number of entries, or the separately maintained fleet count in the Java and Python versions.

For example, after sorting, a sequence of independent arrival times might be:

2.5, 4.0, 5.0

All three values are strictly increasing, so they represent three fleets. If a later car has arrival time 3.0, it is absorbed by the fleet with arrival time 4.0 because:

3.0 <= 4.0

Proof of Correctness

We prove that the algorithm returns the correct number of car fleets.

Invariant

After processing any prefix of cars ordered from closest to farthest from the target, the stored arrival times represent exactly the distinct fleets formed by those cars. These times are strictly increasing in processing order.

Base Case

The first processed car is the closest to the target. No car is ahead of it, so it must form one fleet. Its arrival time is stored, and the invariant holds.

Inductive Step

Assume the invariant holds before processing a new car. Let:

• currentTime be the new car’s independent arrival time.
• lastFleetTime be the arrival time of the fleet immediately ahead.

There are two cases:

1. currentTime <= lastFleetTime

   The current car would reach the target no later than the fleet ahead. Because cars cannot pass, it must catch that fleet before or exactly at the target. It does not create a new fleet, and the existing fleet representation remains correct.

2. currentTime > lastFleetTime

   The current car reaches the target later than the fleet ahead. It cannot catch that fleet before the target, so it remains separate and creates a new fleet. Storing its arrival time preserves the strictly increasing order.

In both cases, the invariant remains true.

Conclusion

After all cars are processed, every stored arrival time corresponds to exactly one fleet, and every fleet is represented once. Therefore, the algorithm returns the correct number of fleets.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 739: Daily Temperatures
• LeetCode 1475: Final Prices With a Special Discount in a Shop
• LeetCode 1673: Find the Most Competitive Subsequence
• LeetCode 907: Sum of Subarray Minimums

These problems maintain a stack with an ordered property and remove or ignore states that can no longer affect the answer. In Car Fleet, the stack-like structure stores increasing fleet arrival times and absorbs cars whose times do not exceed the latest fleet boundary. The same monotonic reasoning enables linear scans after sorting or preprocessing.

Reference Implementation

C++ Solution for LeetCode 853

1class Solution {
2public:
3    int carFleet(int target, vector<int>& position, vector<int>& speed) {
4        vector<pair<int, int>> cars;
5        for (int i = 0; i < static_cast<int>(position.size()); ++i) {
6            cars.push_back({position[i], speed[i]});
7        }
8
9        sort(cars.begin(), cars.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
10            return a.first > b.first;
11        });
12
13        vector<long double> fleetArrivalTimes;
14        for (const auto& car : cars) {
15            long double arrivalTime =
16                static_cast<long double>(target - car.first) / car.second;
17
18            if (fleetArrivalTimes.empty() || arrivalTime > fleetArrivalTimes.back()) {
19                fleetArrivalTimes.push_back(arrivalTime);
20            }
21        }
22
23        return static_cast<int>(fleetArrivalTimes.size());
24    }
25};

The C++ implementation sorts cars by decreasing position and stores fleet arrival times as long double. A new fleet is pushed only when its arrival time is strictly greater than the latest stored fleet time.

Java Solution for LeetCode 853

1class Solution {
2    public int carFleet(int target, int[] position, int[] speed) {
3        int n = Math.min(position.length, speed.length);
4        Car[] cars = new Car[n];
5
6        for (int i = 0; i < n; i++) {
7            cars[i] = new Car(position[i], speed[i]);
8        }
9
10        java.util.Arrays.sort(cars, (a, b) -> {
11            if (a.position != b.position) {
12                return Integer.compare(b.position, a.position);
13            }
14            return Integer.compare(b.speed, a.speed);
15        });
16
17        int fleets = 0;
18        long lastTimeNum = 0;
19        long lastTimeDen = 1;
20
21        for (Car car : cars) {
22            long timeNum = (long) target - car.position;
23            long timeDen = car.speed;
24
25            if (fleets == 0 || timeNum * lastTimeDen > lastTimeNum * timeDen) {
26                fleets++;
27                lastTimeNum = timeNum;
28                lastTimeDen = timeDen;
29            }
30        }
31
32        return fleets;
33    }
34
35    private static class Car {
36        int position;
37        int speed;
38
39        Car(int position, int speed) {
40            this.position = position;
41            this.speed = speed;
42        }
43    }
44}

The Java implementation represents arrival times as fractions. Cross multiplication compares two arrival times exactly without converting them to floating-point values.

Python Solution for LeetCode 853

1from typing import List, Optional
2
3
4class Solution:
5    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
6        cars = sorted(zip(position, speed), reverse=True)
7
8        fleets = 0
9        last_time_num = 0
10        last_time_den = 1
11
12        for pos, velocity in cars:
13            time_num = target - pos
14            time_den = velocity
15
16            if fleets == 0 or time_num * last_time_den > last_time_num * time_den:
17                fleets += 1
18                last_time_num = time_num
19                last_time_den = time_den
20
21        return fleets

The Python implementation follows the same monotonic arrival-time logic. The reverse=True sort orders cars by decreasing position, and cross multiplication avoids floating-point precision issues.