Problem Description

You are given a set of rectangles and a set of points. Each rectangle has its bottom-left corner fixed at the origin (0, 0) and is defined by its length and height. Your task is to determine how many rectangles contain each given point.

Input Details:

• rectangles[i] = [li, hi]: The i-th rectangle extends from (0, 0) to (li, hi), where li is the length (x-dimension) and hi is the height (y-dimension)
• points[j] = [xj, yj]: The j-th point is located at coordinates (xj, yj)

Containment Rules: A rectangle contains a point if:

• The point's x-coordinate is between 0 and the rectangle's length (inclusive): 0 <= xj <= li
• The point's y-coordinate is between 0 and the rectangle's height (inclusive): 0 <= yj <= hi
• Points on the edges or corners of rectangles are considered contained

Output: Return an array count where count[j] represents the number of rectangles that contain the j-th point.

Solution Approach: The solution groups rectangles by their height values in a dictionary. For each height, it maintains a sorted list of the corresponding lengths. When checking a point (x, y), it iterates through all heights greater than or equal to y (since rectangles with smaller heights cannot contain the point). For each valid height, it uses binary search to count how many rectangles at that height have a length greater than or equal to x.

The key optimization is using bisect_left to efficiently find the position where x would be inserted in the sorted list of lengths, then calculating how many rectangles have length >= x by subtracting this position from the total count.

Intuition

The naive approach would be to check every point against every rectangle, which would take O(n * m) time where n is the number of rectangles and m is the number of points. We need a smarter way to count containment.

The key insight is that for a point (x, y) to be inside a rectangle, the rectangle must satisfy two conditions:

1. Its height must be at least y (height >= y)
2. Its length must be at least x (length >= x)

Since all rectangles start at the origin (0, 0), we can think of this problem geometrically: we need rectangles whose top-right corner is "above and to the right" of our point.

This suggests organizing rectangles by one dimension to make searching easier. If we group rectangles by their height, then for any point (x, y), we only need to check rectangles with height >= y. This eliminates many unnecessary comparisons.

For each valid height group, we still need to count how many rectangles have length >= x. If we pre-sort the lengths within each height group, we can use binary search to quickly find this count. The position where x would be inserted tells us how many rectangles have length < x, so the remaining rectangles have length >= x.

The height constraint naturally filters out invalid rectangles (those too short), while binary search on the sorted lengths efficiently counts valid rectangles within each height group. Since rectangle heights are bounded (typically up to 100 in the problem constraints), iterating through valid heights is manageable, and the binary search makes counting within each group logarithmic rather than linear.

This approach transforms the problem from checking every rectangle individually to a more structured search that leverages sorting and binary search for efficiency.

Learn more about Binary Search and Sorting patterns.

Solution Approach

The implementation uses a dictionary-based grouping strategy combined with binary search for efficient counting.

Step 1: Organize Rectangles by Height

d = defaultdict(list)
for x, y in rectangles:
    d[y].append(x)

We create a dictionary where each key is a height value, and the corresponding value is a list of lengths for rectangles with that height. This groups rectangles that share the same height together, making it easier to query them later.

Step 2: Sort Length Lists

for y in d.keys():
    d[y].sort()

For each height group, we sort the list of lengths in ascending order. This preprocessing step enables us to use binary search later when counting rectangles.

Step 3: Process Each Point

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)

For each point (x, y):

• Initialize a counter cnt to 0
• Iterate through all valid heights from y to 100 (the upper bound of rectangle heights)
• For each height h >= y, retrieve the sorted list of lengths xs = d[h]
• Use bisect_left(xs, x) to find the insertion position of x in the sorted list
• The number of rectangles at height h that contain the point is len(xs) - bisect_left(xs, x)

How Binary Search Works Here:

bisect_left(xs, x) returns the leftmost position where x could be inserted to maintain sorted order. This position tells us how many elements in xs are strictly less than x. Therefore:

• If bisect_left(xs, x) returns position i, there are i rectangles with length < x
• The remaining len(xs) - i rectangles have length >= x, which are the ones that contain our point

Time Complexity:

• Preprocessing: O(n log n) where n is the number of rectangles (for sorting)
• Per point query: O(h * log n) where h is the maximum height (typically 100)
• Total: O(n log n + m * h * log n) where m is the number of points

The algorithm efficiently handles the containment check by reducing it to a height filtering step followed by binary searches on pre-sorted length lists.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• Rectangles: [[4, 2], [3, 3], [5, 3], [2, 1]]
• Points: [[3, 2], [1, 3]]

Step 1: Organize Rectangles by Height

We group rectangles by their height values:

• Height 1: Rectangle [2, 1] → length = 2
• Height 2: Rectangle [4, 2] → length = 4
• Height 3: Rectangles [3, 3] and [5, 3] → lengths = 3, 5

Our dictionary d becomes:

d = {
    1: [2],
    2: [4],
    3: [3, 5]
}

Step 2: Sort Length Lists

After sorting (already sorted in this case):

d = {
    1: [2],
    2: [4],
    3: [3, 5]  # sorted: [3, 5]
}

Step 3: Process Each Point

For Point 1: (3, 2)

• We need rectangles with height ≥ 2 and length ≥ 3
• Check height 2: lengths = [4]
  • bisect_left([4], 3) = 0 (3 would be inserted at position 0)
  • Count: 1 - 0 = 1 rectangle (the one with length 4)
• Check height 3: lengths = [3, 5]
  • bisect_left([3, 5], 3) = 0 (3 already exists at position 0)
  • Count: 2 - 0 = 2 rectangles (both length 3 and 5)
• Total for point (3, 2): 1 + 2 = 3 rectangles

For Point 2: (1, 3)

• We need rectangles with height ≥ 3 and length ≥ 1
• Check height 3: lengths = [3, 5]
  • bisect_left([3, 5], 1) = 0 (1 would be inserted at position 0)
  • Count: 2 - 0 = 2 rectangles (both satisfy length ≥ 1)
• Total for point (1, 3): 2 rectangles

Visual Representation:

Height
  3 |  +-----+  +-------+
    |  |     |  |       |
  2 |  | Rect3| | Rect4 |
    |  |[3,3]|  | [5,3] |
  1 |  +-----+  +-------+
    |  +----+   
    |  |Rect1|  +---------+
    |  |[2,1]|  | Rect2   |
  0 +--+----+---+-[4,2]---+--------> Length
    0  1    2   3    4    5
       ^        ^
       |        |
    Point2   Point1
    (1,3)    (3,2)

Point (3, 2) is contained by rectangles [4, 2], [3, 3], and [5, 3]. Point (1, 3) is contained by rectangles [3, 3] and [5, 3].

Final Output: [3, 2]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n + m * h * log n) where n is the number of rectangles, m is the number of points, and h is the range of possible heights (in this case, 101).

• Building the dictionary d takes O(n) time to iterate through all rectangles
• Sorting all the x-coordinates for each unique height takes O(n log n) in the worst case when all rectangles have different heights
• For each of the m points, we iterate through heights from y to 100 (at most 101 iterations)
• For each height, we perform a binary search using bisect_left which takes O(log k) where k is the number of rectangles at that height
• In the worst case, all rectangles could be at the same height, making each binary search O(log n)
• Total query time: O(m * h * log n)

Space Complexity: O(n)

• The dictionary d stores all n rectangle x-coordinates grouped by their y-coordinates, using O(n) space
• The answer list ans uses O(m) space but this is typically considered as output space
• The auxiliary space used by sorting is O(1) since we sort in-place
• Overall auxiliary space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Boundary Interpretation

The Pitfall: A common mistake is misunderstanding what bisect_left returns and how to use it for counting elements >= x. Developers might incorrectly use bisect_right or misinterpret the index returned.

# INCORRECT: Using bisect_right when we need elements >= x
count += len(widths) - bisect_right(widths, point_x)  # Wrong!

# INCORRECT: Forgetting to subtract from total length
count += bisect_left(widths, point_x)  # This gives elements < x, not >= x

The Solution: Remember that bisect_left(arr, x) returns the leftmost position where x could be inserted, which equals the count of elements strictly less than x. To get elements >= x, subtract this from the total length:

# CORRECT: Elements >= x = total - (elements < x)
count += len(widths) - bisect_left(widths, point_x)

2. Hardcoding the Height Upper Bound

The Pitfall: The code assumes rectangle heights are at most 100, which works for the LeetCode problem but creates a brittle solution:

# Hardcoded upper bound - fails if constraints change
for rectangle_height in range(point_y, 101):

The Solution: Make the solution more robust by determining the actual maximum height:

# Better approach: Find actual max height
max_height = max(height for _, height in rectangles) if rectangles else 0

for rectangle_height in range(point_y, max_height + 1):
    # ... rest of the logic

3. Not Handling Edge Cases with Empty Data

The Pitfall: The code doesn't explicitly handle cases where there are no rectangles at a particular height, though defaultdict saves us here:

# This works due to defaultdict, but could be clearer
widths_at_height = height_to_widths[rectangle_height]  # Returns empty list if key doesn't exist

The Solution: While the current code works, being explicit about empty cases improves readability:

# More explicit handling
if rectangle_height in height_to_widths:
    widths_at_height = height_to_widths[rectangle_height]
    count += len(widths_at_height) - bisect_left(widths_at_height, point_x)
# No need for else clause since we're adding 0 anyway

4. Forgetting to Sort After Grouping

The Pitfall: Binary search requires sorted data. Forgetting to sort the width lists after grouping would cause incorrect results:

# WRONG: Forgetting to sort
height_to_widths = defaultdict(list)
for width, height in rectangles:
    height_to_widths[height].append(width)
# Missing: sorting step!

The Solution: Always sort the lists before using binary search. Consider sorting during insertion if rectangles are processed one at a time:

# Option 1: Sort after all insertions (current approach)
for height in height_to_widths.keys():
    height_to_widths[height].sort()

# Option 2: Use bisect.insort for maintaining sorted order during insertion
from bisect import insort
for width, height in rectangles:
    insort(height_to_widths[height], width)

5. Performance Degradation with Sparse Heights

The Pitfall: When rectangle heights are sparse (e.g., only heights 1, 50, and 100 exist), iterating through all values from point_y to 100 wastes time:

# Inefficient when heights are sparse
for rectangle_height in range(point_y, 101):  # Checks many empty heights

The Solution: Iterate only through heights that actually exist:

# More efficient for sparse data
valid_heights = sorted([h for h in height_to_widths.keys() if h >= point_y])
for rectangle_height in valid_heights:
    widths_at_height = height_to_widths[rectangle_height]
    count += len(widths_at_height) - bisect_left(widths_at_height, point_x)