Count Number of Rectangles Containing Each Point — LeetCode 2250 Python Solution

The problem

You are given a 2D integer array rectangles where rectangles[i] = [li, hi] indicates that ith rectangle has a length of li and a height of hi. You are also given a 2D integer array points where points[j] = [xj, yj] is a point with coordinates (xj, yj).

Example

Input

rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]

Output

[2,1]

Explanation

The first rectangle contains no points.

Python solution

class Solution:
    def countRectangles(
        self, rectangles: List[List[int]], points: List[List[int]]
    ) -> List[int]:
        d = defaultdict(list)
        for x, y in rectangles:
            d[y].append(x)
        for y in d.keys():
            d[y].sort()
        ans = []
        for x, y in points:
            cnt = 0
            for h in range(y, 101):
                xs = d[h]
                cnt += len(xs) - bisect_left(xs, x)
            ans.append(cnt)
        return ans

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 2250. Count Number of Rectangles Containing Each Point is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems