Solutions

# Sort (car, pos) by pos, compute each of the car arrival time, loop through arrival times in reverse to compute fleets.
# stack

# O(n log n) time | O(n) space
def carFleet(target: int, position: list[int], speed: list[int]) -> int:
    cars = sorted(zip(position, speed), key=lambda x: x[0])     # sort by position
    arrival_times = [(target - pos) / spd for pos, spd in cars] # compute arrival times, sorted by position
    
    fleets = 0
    last_arrival_time = 0.0
    for curr_time in reversed(arrival_times): # loop from car closest to target to furthest
        if curr_time > last_arrival_time:
            fleets += 1
            last_arrival_time = curr_time
    
    return fleets

# Stack approach
# O(n log n) time | O(n) space
def carFleet(target: int, position: list[int], speed: list[int]) -> int:
    pair = [(p, s) for p, s in zip(position, speed)]
    pair.sort(reverse=True)
    stack = [] # will hold arrival times
    for p, s in pair:  # Reverse order: from car closest to target to furthest
        stack.append((target - p) / s)
        if len(stack) >= 2 and stack[-1] <= stack[-2]:
            stack.pop()
    return len(stack)