Car Fleet

Difficulty: Medium Source: NeetCode

Problem

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer arrays position and speed, both of length n, where position[i] is the starting mile of the i-th car and speed[i] is the speed in miles per hour of the i-th car.

A car cannot pass another car, but it can catch up to it and then travel at the slower car’s speed.

Two or more cars traveling at the same position and same speed form a single car fleet.

If a car catches up to a car fleet at the moment the fleet reaches the target, it does not join the fleet.

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

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

Example 3: Input: target = 100, position = [0,2,4], speed = [4,2,1] Output: 1

Constraints:

n == position.length == speed.length

1 <= n <= 10^5

0 < target <= 10^6

0 <= position[i] < target

All values of position are unique.

1 <= speed[i] <= 10^6

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack — Used here to track fleet formation as you scan cars from front to back.
Sorting — The cars must be processed in order of starting position.

Cars closer to the target have the right of way — if a car behind is faster, it catches up and joins the fleet of the car ahead, adopting its (slower) speed. The key insight: compute how long each car takes to reach the target (time = (target - position) / speed). Then process cars from closest to the target to farthest. If a car behind takes more time than the car ahead, it can never catch up — it is a new fleet. If it takes less or equal time, it merges with the fleet ahead.

A stack of fleet arrival times makes this clean: push a car’s time only if it is strictly greater than the current top (meaning it forms a new fleet). The number of entries in the stack at the end is the answer.

Algorithm

Pair up (position[i], speed[i]) and sort by position in descending order (closest to target first).
Initialize an empty stack.
For each car, compute time = (target - pos) / speed.
If the stack is empty or time > stack[-1], push time (new fleet).
Otherwise, this car catches up to the fleet ahead — skip it (do not push).
Return len(stack).

Solution

def carFleet(target, position, speed):
    # Pair and sort by position descending (car closest to target first)
    pairs = sorted(zip(position, speed), reverse=True)
    stack = []

    for pos, spd in pairs:
        time = (target - pos) / spd
        # Only a new fleet if this car takes longer than the current front fleet
        if not stack or time > stack[-1]:
            stack.append(time)
        # If time <= stack[-1], the car catches up and joins the fleet ahead

    return len(stack)


# Test cases
print(carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3]))  # Expected: 3
print(carFleet(10, [3], [3]))                             # Expected: 1
print(carFleet(100, [0, 2, 4], [4, 2, 1]))               # Expected: 1

# Edge: two cars, faster behind catches up
print(carFleet(10, [0, 4], [2, 1]))   # Expected: 1
# Edge: two cars, faster behind does NOT catch up
print(carFleet(10, [4, 0], [1, 2]))   # Expected: 2

Complexity

Time: O(n log n) — dominated by sorting.
Space: O(n) — for the sorted pairs and stack.

Common Pitfalls

Sorting in ascending order instead of descending. You need to process the car closest to the target first. Sort by position descending.

Using integer division. Time calculations need floating point — (target - pos) / speed should be regular division, not //. A car at position 9 with speed 2 heading to target 10 takes 0.5 hours, which integer division would round to 0.

Thinking you need to actually simulate the fleet merging. You never need to update speeds or positions. The time-to-target comparison is enough: if a car behind takes less time, it physically catches up and joins, no matter where they are.

Note Book