Here is solutions for Car Fleet problem.

1. Understand the problem

A car fleet is a group of cars driving together at the slowest speed among them

=> Because faster cars cannot pass slower cars; if a faster car catches up, they form a fleet.

2. Clarify Constraints (Ask Questions)

1. Positions sorted?

• Not guaranteed. Need to sort cars by position descending (closest to target first).

1. Time to calculate fleets?

• O(n log n) acceptable since n ≤ 10⁵.

1. Do two cars starting at same position merge immediately?

• Yes, even if speeds differ (faster never ahead).

1. Edge case: One car or empty list?

• Return 1 or 0, respectively.

3. Idea

• Find the same time with the formula.

time = (target - position[i]) / speed[i]

Note: If a car behind (farther from target) takes less or equal time to reach the target than the car in front, it must catch up before or at the target.

4. Brainstorm 2-3 ideas

4.1. Naive Solution - O(range * cars).

• Start from [start, target] => Find second by second the time the car meet with each other

=> Union group and count it.

• Time: O(range * cars).

• Space: O(range).

4.2. Stack

• Time: O(N).

• Space: O(N).

5. Implement solutions

5.1. Stack - O(NlogN)

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

        stack = []
        for pos, spd in cars:
            time = (target - pos) / spd
            # If this car arrives later than the fleet ahead → new fleet
            if not stack or time > stack[-1]:
                stack.append(time)

        return len(stack)

• Time: O(NlogN).

• Space: O(N).

5.2. Use previous, current value - O(NlogN)

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pair = [(p, s) for p, s in zip(position, speed)]
        pair.sort(reverse=True)

        fleets = 1
        prevTime = (target - pair[0][0]) / pair[0][1]
        for i in range(1, len(pair)):
            currCar = pair[i]
            currTime = (target - currCar[0]) / currCar[1]
            if currTime > prevTime:
                fleets += 1
                prevTime = currTime
        return fleets

• Time: O(NlogN).

• Space: O(N).

6. Dry run solutions