Problem Statement

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 i-th car and speed[i] is the speed of the i-th 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 (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 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.

Additional information

• n == position.length == speed.length
• 1 <= n <= 10^5
• 0 < target <= 10^6
• 0 <= position[i] < target
• 0 < speed[i] <= 10^6

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 each other 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 each other at 6. The fleet moves at speed 1 until it reaches target.

Example 2:

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

Output: 1

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) catch up to the car starting at 4 (speed 1). All three arrive at the destination together.

Sorting & Linear Scan (Brute Force Logic)

Intuition
A true simulation (moving cars second by second) is impossible because time is continuous and the target can be very far away. Instead, we can calculate the time it takes for each car to reach the target: .

Cars that start closer to the target should be processed first because they act as "blockers" for cars behind them. If a car behind arrives sooner (smaller time) than the car in front, it will catch up and become part of that fleet. It cannot pass. Therefore, its arrival time effectively becomes the same as the slower car in front.

Algorithm

1. Combine position and speed into pairs and sort them by position in descending order (closest to target first).
2. Calculate the time to reach the target for the first car (closest to target) and count it as the first fleet. Store this as current_fleet_time.
3. Iterate through the rest of the cars (moving backwards from the target):

• Calculate the time for the current car.

• If current_car_time > current_fleet_time:

• This car arrives later than the fleet in front. It cannot catch up. It forms a new fleet.

• Update current_fleet_time to this car's time.

• Increment the fleet count.

• If current_car_time <= current_fleet_time:

• This car arrives sooner (or same time), meaning it catches up to the fleet in front. We do nothing (it joins the current fleet).

4. Return the count.

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    # Pair position and speed, then sort by position descending
    pairs = sorted(zip(position, speed), reverse=True)
    
    fleets = 0
    current_fleet_time = 0
    
    for p, s in pairs:
        time = (target - p) / s
        
        # If this car takes longer than the fleet in front, it starts a new fleet
        if time > current_fleet_time:
            fleets += 1
            current_fleet_time = time
            
    return fleets

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: Sorting the cars takes O(n log n). The linear scan takes O(n).

• Space complexity: O(n)

• Reason: Storing the paired list of positions and speeds.

Monotonic Stack (Optimal)

Intuition
This problem can also be modeled using a Monotonic Stack. We sort the cars by position (descending) and iterate through them. We calculate the arrival time for each car and push it onto the stack.

The stack effectively holds the "leaders" of the fleets. If the current car's arrival time is less than or equal to the car at the top of the stack (the car directly in front of it), it means the current car catches up. Since it joins the fleet, we don't need to count it separately-we can pop it from the stack (or simply not push it, depending on implementation). Wait, actually, the standard stack logic is: push every car, and if the new top is faster than the one below it, pop it.

Algorithm

1. Create pairs of (position, speed) and sort them in descending order of position.
2. Initialize an empty stack.
3. Iterate through each car:

• Calculate time = (target - position) / speed.
• Push time onto the stack.
• Check for collision: If the stack has at least 2 items, compare the top two.
• If stack[-1] <= stack[-2] (Current car arrives sooner/same time as the car in front):
• The current car catches up. Pop it from the stack (it merges into the fleet led by stack[-1]).

4. The length of the stack represents the number of distinct fleets.

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    pair = sorted(zip(position, speed), reverse=True)
    stack = []
    
    for p, s in pair:
        time = (target - p) / s
        stack.append(time)
        
        # If the current car arrives faster (smaller time) than the one before it,
        # it catches up. Pop it.
        if len(stack) >= 2 and stack[-1] <= stack[-2]:
            stack.pop()
            
    return len(stack)

Time & Space Complexity

• Time complexity: O(n log n)

• Reason: Sorting dominates the complexity. The stack operations are O(n).

• Space complexity: O(n)

• Reason: Storing the pairs and the stack.