MediumNeetCode150ArrayStackSortingGreedy

Car Fleet

Return number of car fleets that arrive at target.

Examples

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

Fleets: [10,8] -> arrive at 6, [5,3] -> arrive at 7, [0] -> arrives at 4.

Constraints

  • •1 <= position.length, speed.length <= 10^5
  • •position.length == speed.length
  • •1 <= target <= 10^6

Approaches

Sort by position, simulate.

CodeT: O(n log n) | S: O(n)
def carFleet(target, position, speed):
    n=len(position); cars=sorted(zip(position,speed))
    times=[(target-p)/s for p,s in cars]
    fleets=0; mx=0
    for t in reversed(times):
        if t>mx: fleets+=1; mx=t
    return fleets

Same approach.

CodeT: O(n log n) | S: O(n)
def carFleet(target, position, speed):
    cars=sorted(zip(position,speed),reverse=True)
    fleets=0; mx=0
    for p,s in cars:
        t=(target-p)/s
        if t>mx: fleets+=1; mx=t
    return fleets

Same approach.

Diagram

Sort by position desc, track slowest time per fleet
CodeT: O(n log n) | S: O(n)

Complexity Comparison

Sort + Simulate
T: O(n log n)S: O(n)

Sort by position, simulate.

Sort + Reverse
T: O(n log n)S: O(n)

Same approach.

Sort - Optimized
T: O(n log n)S: O(n)

Same approach.

Common Mistakes

Wrong sort direction

Floating point comparison

Off-by-one in fleet count

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems