LeetEye LeetEye
Medium Stack ~5 min

Car Fleet

stack 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 then travel at the same speed. The faster car will slow down to match the slower car's speed.

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

If a car catches up to a car fleet right at the destination point, it still counts as one fleet.

Return the number of car fleets that will arrive at the destination.

Examples

Example 1
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Example 2
Input: target = 10, position = [3], speed = [3]
Output: 1
Key Insight

Calculate arrival time for each car. Process from position closest to target backward.

Sort cars by position (front first). Car joins fleet ahead if its arrival time ≤ fleet's time, else forms new fleet. Count distinct fleet times.

How to Approach This Problem

Pattern Recognition: When you see keywords like car fleet stack, think Stack.

Step-by-Step Reasoning

1 For a car at position p with speed s, time to reach target T is:
Answer: (T - p) / s
Distance to travel = T - p. Time = distance / speed.
2 We process cars from closest to target because:
Answer: Front cars can block/slow down cars behind them
A slower car in front creates a "barrier" — faster cars behind can only match its arrival time, not beat it.
3 Car B (behind) merges with Car A (ahead) if:
Answer: B would arrive at target before or at same time as A
If B's arrival time ≤ A's, B catches up (or ties at target). B can't pass A, so B joins A's fleet.
4 When car B merges with car A's fleet:
Answer: Fleet takes A's (slower) arrival time
B can't pass A, so B slows down to A's pace. Fleet arrival = A's original arrival time.
5 The stack stores:
Answer: Arrival times of fleet "leaders"
Each stack entry represents a fleet. We track its arrival time to compare with the next car.

Solution

def carFleet(target: int, position: List[int], speed: List[int]) -> int:
    # Pair positions with arrival times, sort by position descending
    cars = sorted(zip(position, speed), reverse=True)
    stack = []  # Arrival times of fleet leaders
    
    for pos, spd in cars:
        arrival_time = (target - pos) / spd
        
        # If this car arrives later than the fleet ahead, it's a new fleet
        if not stack or arrival_time > stack[-1]:
            stack.append(arrival_time)
        # Otherwise, it merges with the fleet ahead (don't push)
    
    return len(stack)

Complexity Analysis

Time O(n log n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Stack problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye