Car Fleet LeetCode solution in Python

1
# Runtime: 1570 ms (Top 45.22%) | Memory: 36.4 MB (Top 42.14%)
2
class Solution:
3
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
4
        def computeArrivalTime(curr_pos, curr_speed):
5
            nonlocal target
6
            return (target - curr_pos) / curr_speed
7
            # avoid integer division, as a car may arrive at 5.2s and another at 5.6s
8

9
        cars = list(zip(position, speed))
10
        cars.sort(key=lambda x: x[0], reverse=True)
11
        arrival_bound = None  # time upper bound
12
        fleet = 0
13
        for pos, sp in cars:
14
            curr_arrival = computeArrivalTime(pos, sp)
15
            if not arrival_bound or curr_arrival > arrival_bound:
16
                arrival_bound = curr_arrival
17
                fleet += 1
18
        return fleet
19

20
    # time O(n logn): sort = (nlogn); loop = (n)
21
    # space O(n): depend on sort