Car Fleet — Monotonic Stack Pattern— Neetcode 150

Problem: Car Fleet

Link: https://leetcode.com/problems/car-fleet/description/

Difficulty: Medium

Topics: List, Stack

Pattern: Monotonic Stack

Intuition

The key idea I figured out was that instead of tracking cars directly, it’s easier to track how long each car takes to reach the target.

If two cars end up reaching the target at the same time (or one earlier than the other), they form a fleet — even if they start at different positions.

So the problem naturally reduces to time comparison.

Steps

1. Pair position and speed, then sort them in descending order of position.
2. For each pair:

• Calculate the time to reach the target.
• Push the time onto the stack.

1. If the top of the stack is less than or equal to the previous value, pop it — the cars merge into one fleet.
2. The final stack size gives the number of fleets.

Complexity

• Time Complexity: O(n log n) — sorting dominates
• Space Complexity: O(n) — stack usage

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

        stack = []
        for p, s in pair:
            stack.append(float(target-p)/s)
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop()
        return len(stack)