LeetCode 853 - Car Fleet

LeetCode Problem 853

Difficulty: 🟡 Medium
Topics: Array, Stack, Sorting, Monotonic Stack

Solution

Problem Understanding

The problem describes a set of cars driving toward the same destination, represented by the integer target. Each car starts at a unique position and moves at a constant speed. Cars cannot overtake each other. If a faster car catches up to a slower car ahead of it, the faster car must slow down and continue traveling together with the slower car. Once this happens, they form a single car fleet.

The task is to determine how many distinct fleets will eventually arrive at the target.

The input consists of:

• target, the destination position on the road.
• position[i], the starting location of the i-th car.
• speed[i], the speed of the i-th car.

The output is a single integer representing the number of fleets that reach the target.

A key detail is that if two cars meet exactly at the target position, they are still considered part of the same fleet. This affects comparisons when determining whether cars merge.

The constraints are important because they rule out inefficient simulations:

• Up to 10^5 cars can exist.
• Positions and speeds can both be large.
• All positions are unique.

Since n can be very large, any solution worse than roughly O(n log n) will likely time out. This immediately suggests that repeatedly simulating movement over time is not practical.

Several edge cases are important:

• A single car should always produce exactly one fleet.
• Cars already ordered by increasing arrival times never merge.
• Multiple cars can merge into one large fleet.
• A faster car behind a slower car may catch it exactly at the destination, and this still counts as one fleet.
• Because positions are unique, we never need to handle ties in starting locations.

Approaches

Brute Force Approach

A straightforward idea is to simulate the cars moving toward the target over time. At each moment, we could check whether one car catches another and merge them into fleets dynamically.

This approach is conceptually correct because it directly models the problem definition. However, it becomes extremely inefficient. Cars move continuously, and determining exactly when collisions happen requires repeated comparisons between cars and recalculations after merges.

Another brute-force variant is to compare every pair of cars and determine whether one catches another before the target. This requires considering interactions transitively, because fleets formed earlier affect later cars.

In the worst case, these approaches require O(n^2) comparisons or complicated simulations, which is too slow for n = 10^5.

Optimal Approach

The key insight is that we do not actually need to simulate movement.

For each car, we can compute the time required to reach the target:

$$\text{time} = \frac{target - position}{speed}$$

Now consider cars ordered from closest to the target to farthest away.

If a car behind takes less than or equal time to reach the destination than the car ahead, it must eventually catch up before or exactly at the target. Therefore, they form the same fleet.

If the car behind takes strictly longer, it can never catch the fleet ahead, so it forms a new fleet.

This observation allows us to process cars in reverse positional order while tracking the maximum arrival time seen so far. The pattern behaves like a monotonic stack, because fleet times are non-decreasing as we move backward.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Simulates interactions or compares all pairs
Optimal	O(n log n)	O(n)	Sort by position, process arrival times greedily

Algorithm Walkthrough

1. Pair each car's position with its speed.

We need to process cars based on their location on the road. Since positions are unique, sorting gives a clear driving order. 2. Sort the cars by position in ascending order.

After sorting, the car closest to the target appears last. This ordering allows us to process cars from front to back when iterating in reverse. 3. Iterate through the cars from right to left.

We start with the car nearest the target because no car can influence it from ahead. 4. Compute the arrival time for the current car.

The formula is:

$t = \frac{target - position}{speed}$

This represents how long the car would take to reach the destination if it never slowed down. 5. Compare the current arrival time with the latest fleet arrival time.

• If the current car's time is greater, it cannot catch the fleet ahead. Therefore, it forms a new fleet.
• If the current car's time is less than or equal to the fleet ahead's time, it merges into that fleet.

6. Maintain the maximum arrival time encountered so far.

This value represents the arrival time of the most recent fleet. 7. Count how many distinct fleets are formed.

Every time we encounter a larger arrival time, we increment the fleet count.

Why it works

Processing from nearest to farthest is the crucial idea. Every fleet ahead acts like a moving barrier. A car behind can only either merge into that fleet or remain separate.

If the rear car reaches the target sooner than the fleet ahead, it must catch up before arriving. Since overtaking is impossible, the rear car merges into that fleet and inherits its slower arrival time.

Therefore, the sequence of fleet arrival times is monotonically increasing when scanning backward through the sorted cars. Counting how many times the arrival time increases gives the exact number of fleets.

Python Solution

from typing import List

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed))

        fleets = 0
        latest_time = 0.0

        for pos, spd in reversed(cars):
            arrival_time = (target - pos) / spd

            if arrival_time > latest_time:
                fleets += 1
                latest_time = arrival_time

        return fleets

The implementation starts by combining positions and speeds into pairs using zip. Sorting these pairs by position gives the cars in road order.

The loop iterates in reverse because we want to process cars from closest to the target toward the farthest. For each car, the code computes the time required to reach the target.

The variable latest_time stores the arrival time of the fleet currently ahead. If the current car would arrive later than that fleet, it cannot catch up and must form a new fleet. Otherwise, it merges into the existing fleet.

The variable fleets counts how many distinct fleets exist.

Go Solution

package main

import (
	"sort"
)

func carFleet(target int, position []int, speed []int) int {
	type Car struct {
		position int
		speed    int
	}

	n := len(position)
	cars := make([]Car, n)

	for i := 0; i < n; i++ {
		cars[i] = Car{
			position: position[i],
			speed:    speed[i],
		}
	}

	sort.Slice(cars, func(i, j int) bool {
		return cars[i].position < cars[j].position
	})

	fleets := 0
	latestTime := 0.0

	for i := n - 1; i >= 0; i-- {
		arrivalTime := float64(target-cars[i].position) / float64(cars[i].speed)

		if arrivalTime > latestTime {
			fleets++
			latestTime = arrivalTime
		}
	}

	return fleets
}

The Go implementation follows the same logic as the Python version. A custom Car struct stores each car's position and speed together.

The cars are sorted using sort.Slice. Since Go performs integer division by default, the code explicitly converts values to float64 before computing arrival times.

No special handling for nil slices is required because the problem guarantees valid input arrays of equal length.

Worked Examples

Example 1

Input:

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

First, pair and sort the cars:

Position	Speed
0	1
3	3
5	1
8	4
10	2

Now process from right to left.

Car	Arrival Time	Latest Fleet Time	Action	Fleets
(10,2)	1	0	New fleet	1
(8,4)	1	1	Merge	1
(5,1)	7	1	New fleet	2
(3,3)	3	7	Merge	2
(0,1)	12	7	New fleet	3

Final answer: 3

Example 2

Input:

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

Car	Arrival Time	Latest Fleet Time	Action	Fleets
(3,3)	7/3	0	New fleet	1

Final answer: 1

Example 3

Input:

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

Sorted cars:

Position	Speed
0	4
2	2
4	1

Process backward:

Car	Arrival Time	Latest Fleet Time	Action	Fleets
(4,1)	96	0	New fleet	1
(2,2)	49	96	Merge	1
(0,4)	25	96	Merge	1

Final answer: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Storing paired car data requires extra space

The algorithm spends most of its time sorting the cars by position. The subsequent reverse traversal is linear. Since sorting n elements requires O(n log n) time, this becomes the overall complexity.

The auxiliary space comes from storing paired (position, speed) data. Aside from that, only a few scalar variables are used.

Test Cases

from typing import List

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed))

        fleets = 0
        latest_time = 0.0

        for pos, spd in reversed(cars):
            arrival_time = (target - pos) / spd

            if arrival_time > latest_time:
                fleets += 1
                latest_time = arrival_time

        return fleets

sol = Solution()

assert sol.carFleet(12, [10,8,0,5,3], [2,4,1,1,3]) == 3
# Standard example with multiple merges

assert sol.carFleet(10, [3], [3]) == 1
# Single car case

assert sol.carFleet(100, [0,2,4], [4,2,1]) == 1
# All cars merge into one fleet

assert sol.carFleet(10, [0,4,8], [2,2,2]) == 3
# Equal speeds, no car can catch another

assert sol.carFleet(10, [6,8], [3,2]) == 2
# Faster rear car still cannot catch before target

assert sol.carFleet(10, [6,8], [4,2]) == 1
# Rear car catches exactly at target

assert sol.carFleet(20, [5,10,15], [1,1,1]) == 3
# Same speeds with different positions

assert sol.carFleet(20, [5,10,15], [3,2,1]) == 1
# Cascading merge into one fleet

assert sol.carFleet(15, [1,2,3,4,5], [5,4,3,2,1]) == 1
# Increasing slowdown causes all cars to merge

assert sol.carFleet(50, [10,20,30,40], [1,2,3,4]) == 4
# Faster cars are already ahead, so no merges

Test	Why
Standard multi-fleet example	Verifies normal fleet merging behavior
Single car	Smallest valid input
All cars merge	Ensures cascading merges work
Equal speeds	Confirms no catching occurs
Cannot catch before target	Validates strict comparison logic
Catch exactly at target	Confirms target merge rule
Same speed sequence	Tests independent fleets
Descending fleet speeds	Tests chain merging
Progressive slowdown	Validates repeated merging
Faster cars already ahead	Ensures position ordering matters

Edge Cases

One important edge case occurs when a car catches another exactly at the destination. A naive implementation might require the rear car to arrive strictly earlier in order to merge. However, the problem explicitly states that meeting at the target still forms one fleet. The implementation handles this correctly because cars merge whenever their arrival time is less than or equal to the fleet ahead's time.

Another subtle case involves equal speeds. If two cars travel at the same speed and start at different positions, the rear car can never catch the front car. A buggy solution might incorrectly merge them if it only compares speeds. This implementation avoids that issue entirely by comparing arrival times instead of raw speeds.

A third important case is cascading merges. A car may merge into a fleet that was itself formed by earlier merges. For example, car A merges into car B, and then car C merges into the resulting fleet. Simulating this incorrectly can be complicated, but the monotonic arrival-time approach naturally handles it. Once a fleet forms, its effective arrival time becomes fixed, and all later cars compare against that fleet time.

Another edge case is already sorted or reverse-sorted inputs. Since the algorithm explicitly sorts cars before processing, it does not rely on any initial ordering and remains correct for all valid inputs.