#26 Medium Time O(n log n) Space O(n) Animated

Car Fleet

Determine how many car fleets will arrive at the destination.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern LIFO state for unresolved work

Keep only items whose matching decision has not been made yet.

Approach: Monotonic Stack + Sorting

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Keep only items whose matching decision has not been made yet.

Common Pitfall

Check that the stack is non-empty before reading its top.

Description

Determine how many car fleets will arrive at the destination.

Constraints

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution — Monotonic Stack + Sorting

TimeO(n log n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Read one item at a time.
Push unresolved work.
Match or remove work when its partner arrives.
Validate the final stack state.

def carFleet(target, position, speed):
    pair = [[p, s] for p, s in zip(position, speed)]
    stack = []
    
    for p, s in sorted(pair)[::-1]: # Reverse sorted order
        stack.append((target - p) / s)
        if len(stack) >= 2 and stack[-1] <= stack[-2]:
            stack.pop()
            
    return len(stack)

Daily Temperatures

Largest Rectangle in Histogram

Car Fleet

Steps

Description

Constraints

Tags

Solution — Monotonic Stack + Sorting