LC853. Car Fleet

Approach 1: Optimal

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        fleets = sorted(zip(position, speed), reverse=True)
        stack = []
 
        for pos, speed in fleets:
            # For current car, calc time it takes to reach target
            currTime = (target - pos) / speed
 
            # Top of stack holds car that's closer to target and can form
            # a fleet
            #
            # If current car can catch up to the current fleet, do nothing
            # as it's now bumper-to-bumper and part of current fleet. If it's slower,
            # then it cannot catch up and is now forming a new fleet with some gap from the 
            # existing fleet closer to target.
            if stack and currTime <= stack[-1]:
                continue
            
            stack.append(currTime)
        
        return len(stack)

Complexity

Time: $O(nlogn)$
Space: $O(n)$

Notes

Other Languages