Count Number of Rectangles Containing Each Point LeetCode solution in Python

1
class Solution:
2
    def binarySearch(self, arr, target):
3
        left, right = 0, len(arr)
4
        ans = None
5
        while left < right:
6
            mid = left + ((right - left) // 2)
7
            if arr[mid] >= target:
8
                # Potential answer found! Now try to minimize it iff possible.
9
                ans = mid
10
                right = mid
11
            else:
12
                left = mid + 1
13
        return ans
14

15
    def countRectangles(
16
        self, rectangles: List[List[int]], points: List[List[int]]
17
    ) -> List[int]:
18
        # Sort rectangles based on the lengths
19
        rectangles.sort()
20
        # Group rectangles by their height in increasing order of their length
21
        lengths = {}
22
        for x, y in rectangles:
23
            if y in lengths:
24
                lengths[y].append(x)
25
            else:
26
                lengths[y] = [x]
27

28
        heights = sorted(list(lengths.keys()))
29

30
        count = [0] * len(points)
31

32
        for idx, point in enumerate(points):
33
            x, y = point
34
            # Get the  min height rectangle that would accommodate the y coordinate of current point.
35
            minHeightRectIdx = self.binarySearch(heights, y)
36
            if minHeightRectIdx is not None:
37
                for h in heights[minHeightRectIdx:]:
38
                    # Get the Min length rectangle that would accommodate the x coordinate of current point for all h height rectangles.
39
                    minLenRectIdx = self.binarySearch(lengths[h], x)
40
                    if minLenRectIdx is not None:
41
                        count[idx] += len(lengths[h]) - minLenRectIdx
42

43
        return count