Car Fleet

Problem

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer arrays position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one 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 at 12.
The car starting at 0 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 at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.

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 at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting at 6. The fleet moves at speed 1 until it reaches target.

Constraints:

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

Solution

Approach: Sort by Position + Stack

The key insight is to process cars from the position closest to the target backwards. We calculate the time each car needs to reach the target. If a car behind takes longer or equal time than the car ahead, they form a fleet. Otherwise, the car behind forms a new fleet.

Algorithm:

Pair each car’s position with its time to reach the target
Sort by position in descending order (closest to target first)
Use a stack to track fleet arrival times
If current car’s time > last fleet’s time, it’s a new fleet

Implementation

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Pair position with time to reach target
        cars = [(pos, (target - pos) / spd) for pos, spd in zip(position, speed)]
        # Sort by position (descending - closest to target first)
        cars.sort(reverse=True)

        stack = []
        for pos, time in cars:
            # If this car takes longer than the last fleet, it's a new fleet
            if not stack or time > stack[-1]:
                stack.append(time)
            # Otherwise, it catches up and joins the fleet (don't add to stack)

        return len(stack)

Alternative (Without Stack):

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

        for pos, spd in cars:
            time = (target - pos) / spd
            # If current car takes longer, it's a new fleet
            if time > prev_time:
                fleets += 1
                prev_time = time

        return fleets

Complexity Analysis

Time Complexity: O(n log n), dominated by sorting the cars by position.
Space Complexity: O(n) for storing the car pairs and stack.

Key Insights

Process from Front to Back: We process cars starting from those closest to the target. This is crucial because cars behind can catch up to cars ahead, but not vice versa.
Time-Based Comparison: We calculate time to reach the target for each car: time = (target - position) / speed. If a car behind takes longer than the car ahead, it cannot catch up and forms its own fleet.
Fleet Formation: Cars form a fleet if the car behind would reach the target in less time (or equal time) than the car ahead. The fleet then moves at the speed of the slowest car.
Stack Represents Fleets: Each element in the stack represents a fleet’s arrival time. We only add a new element when we find a car that takes longer than the previous fleet.
No Explicit Merging: We don’t need to explicitly merge fleets. By processing front to back and only pushing slower times, we naturally count distinct fleets.