Python | Simple Binary Search | O(m log k), O(n) | Beats 98%
CodeComplexity

Time complexity: O(m log k). Binary search has range k, which is max(rank) * cars per worker ** 2, time is log(k). Each iteration of binary sear
# Code
```python3 []
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:

        def isValidTime(time):
            cars_done = 0
            for rank, workers in ranks.items():
                # rank * cars ** 2 = time, cars ** 2 = time / rank, cars = sqrt(time / rank)
                cars_done += workers * floor(sqrt(time / rank)) # each worker w/ same rank does same num cars
            return cars_done >= cars # true / false if current time can process enough cars

        ranks = Counter(ranks) # turn ranks into counter for faster isValidTime() check
        
        # min time is 0, max time is if all workers take the most time
        left, right = 0, max(ranks) * ceil(cars / len(ranks)) ** 2
        while left < right: # binary search for minimum possible time
            mid = (left + right) // 2

            if isValidTime(mid):
                right = mid # valid time, move right down
            else:
                left = mid + 1 # invalid time, move left up

        return left # left = right = min possible time. left - 1 is first invalid time
```

# Complexity
- Time complexity: $$O(m\ log\ k)$$. Binary search has range k, which is max(rank) * cars per worker ** 2, time is log(k). Each iteration of binary search calls isValidTime() which iterates over m cars and performs constant operations. Overall time is log(k) * m.

- Space complexity: $$O(n)$$. Converts rank from List into Counter, worst case Counter has all n ranks. All other variables are constant space.

# Performance

![Screenshot (16).png](https://assets.leetcode.com/users/images/a8b05577-eb2c-4c18-ad87-5eded821888b_1742085006.4599283.png)

['Binary Search', 'Python3']