#2250

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Number of Rectangles Containing Each Point

Given a set of rectangles and points, determine how many rectangles contain each point.

array hash table binary search binary indexed tree sorting

Problem Statement

You are given a 2D integer array rectangles, where each entry rectangles[i] = [li, hi] represents a rectangle with its top-right corner at (li, hi) and its bottom-left corner at (0, 0). You are also given a 2D integer array points, where each entry points[j] = [xj, yj] represents a point located at the coordinates (xj, yj).

Your task is to return an integer array count, where count[j] represents the number of rectangles that contain the jth point from the points array. A rectangle contains a point if the point's x-coordinate is less than or equal to the rectangle's x-coordinate and its y-coordinate is less than or equal to the rectangle's y-coordinate.

Examples

Example 1

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

Output: [2,1]

The first rectangle contains no points. The second rectangle contains only the point (2, 1). The third rectangle contains the points (2, 1) and (1, 4). The number of rectangles that contain the point (2, 1) is 2. The number of rectangles that contain the point (1, 4) is 1. Therefore, we return [2, 1].

Example 2

Input: rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]

Output: [1,3]

The first rectangle contains only the point (1, 1). The second rectangle contains only the point (1, 1). The third rectangle contains the points (1, 3) and (1, 1). The number of rectangles that contain the point (1, 3) is 1. The number of rectangles that contain the point (1, 1) is 3. Therefore, we return [1, 3].

Constraints

1 <= rectangles.length, points.length <= 5 * 104
rectangles[i].length == points[j].length == 2
1 <= li, xj <= 109
1 <= hi, yj <= 100
All the rectangles are unique.
All the points are unique.

Solution Approach

Array Scanning with Hash Lookup

By iterating over each point and checking how many rectangles can contain it, we can optimize the process using a hash table to store pre-computed counts. This allows us to quickly reference the number of rectangles that meet the conditions for each point.

Binary Search Optimization

Since the height of rectangles and points is constrained (at most 100), we can use binary search techniques on sorted rectangles or points to limit the number of checks required for each query. This method significantly reduces the time complexity for larger inputs.

Pre-computation for Height

One approach is to precompute counts for different height ranges. Given the constraint on rectangle height and point y-coordinates (both maxing at 100), we can precompute which rectangles are valid for each point, and store these counts in a table for fast access.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach chosen. The brute force solution involves checking every point against all rectangles, leading to O(N*M) complexity, where N is the number of rectangles and M is the number of points. Optimizations such as binary search or pre-computation can reduce this. Space complexity also depends on the approach, with storage for rectangles and points taking O(N + M) space in the worst case.

What Interviewers Usually Probe

Candidate's ability to optimize brute force methods for large inputs.
Awareness of sorting and binary search optimization techniques.
Understanding of hash table usage for efficient lookup and pre-computation.

Common Pitfalls or Variants

Common pitfalls

Incorrectly assuming all rectangles are relevant for each point, leading to excessive checks.
Failure to optimize searching for rectangles by overlooking sorting or binary search options.
Not considering space and time trade-offs when scaling to the upper constraint limits.

Follow-up variants

What if rectangles or points had larger or smaller values?
How would the problem change if rectangles were not guaranteed to have unique dimensions?
How can we modify this approach to handle a dynamically changing set of rectangles or points?

FAQ

What is the main approach for solving the Count Number of Rectangles Containing Each Point problem?

The primary approach involves scanning the array of rectangles and using hash lookups or binary search techniques to efficiently count how many rectangles contain each point.

How can I optimize the brute-force solution to Count Number of Rectangles Containing Each Point?

You can optimize the solution by leveraging binary search on sorted rectangles or points, and by using pre-computation for faster lookups.

What is the maximum time complexity for this problem?

The maximum time complexity occurs when using a brute-force approach, which is O(N*M), where N is the number of rectangles and M is the number of points.

What key patterns should I focus on for this problem?

Key patterns include array scanning plus hash lookup, binary search optimization, and pre-computation based on given constraints.

How can GhostInterview help me with the Count Number of Rectangles Containing Each Point problem?

GhostInterview offers tailored guidance, helping you optimize your approach and providing instant feedback to ensure efficiency and correctness.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#2251 number of flowers in full bloom #2008 maximum earnings from taxi #2501 longest square streak in an array