Car Fleet: Sort and Stack to Count Collisions

LeetCode 853 Car Fleet is one of those problems that looks tricky at first but boils down to a clean pattern once you see the right angle. You have cars on a one-lane road heading toward a target. Faster cars that catch up to slower ones merge into a single "fleet" traveling at the slower speed. Your job: count how many distinct fleets arrive at the target. The key is sorting by position and then comparing arrival times.

The problem

There are n cars on a one-lane road, all heading toward the same target destination. Each car i starts at position[i] and drives at speed[i] miles per hour. A car can never pass another car, but it can catch up and then travel at the same speed as the car ahead. A group of cars moving at the same position and speed is called a "fleet." A single car is also a fleet of one. Return the number of fleets that arrive at the target.

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

Car at position 10 (speed 2) reaches target in 1.0 hours. Car at position 8 (speed 4) also reaches target in 1.0 hours. They form one fleet. Car at position 5 (speed 1) takes 7.0 hours. Car at position 3 (speed 3) takes 3.0 hours, but it catches up to the car at position 5 and slows down, so they form a fleet arriving at 7.0. Car at position 0 (speed 1) takes 12.0 hours and forms its own fleet. Total: 3 fleets.

The brute force

The naive approach is to simulate the cars moving step by step. At each time increment, move every car forward by its speed. If a car catches up to the one ahead, merge them. Keep going until all cars reach the target. Count the remaining groups.

This simulation is expensive. The time to reach the target can be very large, and you need to track every car's position each step. In the worst case with large targets and slow speeds, the time complexity blows up. There is no need for simulation when you can compute everything directly.

The key insight

Here is the idea. A car can only be blocked by a car that is ahead of it (closer to the target). If a car behind would arrive at the target before the car ahead, it must slow down and join that car's fleet. If it would arrive later, it cannot catch up and forms a new fleet.

So the algorithm is:

1. Sort cars by position in descending order (closest to target first).
2. Compute each car's arrival time: (target - position) / speed.
3. Walk through the sorted cars. Maintain the current fleet's arrival time (the slowest car so far). If the next car's arrival time is greater than the current fleet's time, it forms a new fleet.

This is essentially a stack-based greedy approach. You are "stacking" cars into fleets by checking whether each car's arrival time exceeds the current fleet leader's time.

Step-by-step walkthrough

Let's trace through target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3].

Notice a few things:

• Sorting by position descending is crucial. It lets us process cars from front to back. A car can only join the fleet directly ahead of it.
• Arrival time determines fleet membership. If a car's arrival time is less than or equal to the fleet ahead, it catches up and merges. If it is greater, it is too slow and starts a new fleet.
• We only track the current fleet's arrival time. There is no need for a full stack data structure. A single variable tracking the maximum arrival time so far is enough.

The code

def carFleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    fleets = 0
    curr_time = 0

    for pos, spd in cars:
        arrival = (target - pos) / spd
        if arrival > curr_time:
            fleets += 1
            curr_time = arrival

    return fleets

That is 8 lines of logic. Let's break it down:

1. Pair positions with speeds and sort descending by position. Cars closest to the target come first.
2. Track curr_time, the arrival time of the current fleet leader. Start at 0.
3. For each car, compute its arrival time. If it is strictly greater than curr_time, this car cannot catch the fleet ahead. It starts a new fleet, and curr_time updates.
4. If the arrival time is less than or equal to curr_time, this car catches up to the fleet ahead and merges. We do nothing.
5. Return the fleet count.

The if arrival > curr_time check is the heart of it. It is the same "compare against the top of the stack" logic you see in monotonic stack problems, except here a single variable suffices because we only care about the most recent fleet's time.

Complexity analysis

Time: O(n log n). The sort dominates. The single pass through the sorted array is O(n).

Space: O(n). We create the sorted array of pairs. If you sort in-place (for example, by zipping into a list and sorting), the extra space is O(n) for the pairs.

The sort-based approach is both simpler and faster. You trade a simulation loop for a clean one-pass scan after sorting.

Common mistakes

A few things to watch for when implementing this:

1. Sorting in the wrong direction. You need descending order by position. If you sort ascending, you would process the slowest cars first and the comparison logic flips. Descending is more natural because you check each car against the fleet ahead of it.

2. Using integer division instead of float. The arrival time (target - pos) / spd must be a float division. In Python 3 this happens automatically, but in languages like Java or C++, you need to cast to float or double. Integer division truncates and gives wrong fleet groupings.

3. Using >= instead of > for the fleet comparison. If a car arrives at exactly the same time as the fleet ahead, it joins that fleet. Use strict > to start a new fleet only when the car is genuinely slower.

4. Forgetting that a single car is a fleet. Even if a car cannot catch anyone, it is still its own fleet.

The building blocks

This problem is built on two reusable bricks:

Sort to impose order

Many array problems become simpler once you sort the input. Here, sorting by position transforms a scattered set of cars into a linear sequence you can scan once. The same idea appears in Merge Intervals (sort by start), Meeting Rooms (sort by start), and Non-overlapping Intervals.

Greedy scan with a running maximum

After sorting, the core logic is: walk through the array, maintain a running value (here, the current fleet's arrival time), and make a decision at each step. This is the greedy pattern. You commit to the locally optimal choice (merge or new fleet) without backtracking.

curr_time = 0
for pos, spd in sorted_cars:
    arrival = (target - pos) / spd
    if arrival > curr_time:
        fleets += 1
        curr_time = arrival

This is the building block. The only things that change between problems are:

• What you sort by (position, start time, value)
• What you compare (arrival time, end time, interval overlap)
• What decision you make (new fleet, merge interval, remove overlap)

Edge cases

Before submitting, verify your solution handles:

• Single car position = [5], speed = [3]: answer is 1. One car is one fleet.
• All cars at the same position: they all have the same arrival time and form one fleet. Answer is 1.
• Cars already sorted by position descending: the sort is a no-op. The algorithm still works.
• All different speeds but no catching: if every car's arrival time is strictly increasing (after sorting by position descending), every car is its own fleet. Answer is n.
• Two cars, same arrival time: position = [2, 4], speed = [2, 1], target = 6. Times are 2.0 and 2.0. They form one fleet. Answer is 1.

The sort + scan approach handles all of these without special cases.

From understanding to recall

You have read through the sort-and-scan solution. You see how sorting by position and comparing arrival times groups cars into fleets. But can you write it from scratch in an interview three weeks from now?

The pattern is not complicated, but it has a few moving parts: sorting pairs in descending order, computing float arrival times, and the > comparison against the current fleet leader. Under pressure, people sort in the wrong direction, use integer division, or mix up the comparison operator. These are not conceptual mistakes. They are recall mistakes.

Spaced repetition is built for exactly this. Instead of solving Car Fleet once and moving on, you practice the sort-then-scan pattern at increasing intervals. Each time, you write it from scratch. After a few repetitions, it is in your long-term memory and you can apply it to any sort-based greedy variant without hesitation.

Related posts

• Daily Temperatures - Another stack-based problem where processing order and comparisons determine grouping
• Merge Intervals - Uses the same "sort then scan" pattern to merge overlapping intervals
• Sort Colors - A different sorting technique (Dutch National Flag) but reinforces the idea that sorting unlocks simpler algorithms

CodeBricks breaks the sort-and-scan pattern into its reusable pieces and drills them individually. You type the arrival time comparison from scratch each time, building the muscle memory so that when you see Car Fleet or Merge Intervals in an interview, the code flows without hesitation.