Solution Approach

The solution groups rectangles by height and uses binary search to count containing rectangles.

Step 1: Group Rectangles by Height

height_to_widths = defaultdict(list) for width, height in rectangles:  height_to_widths[height].append(width)

Step 2: Sort Width Lists

for height in height_to_widths.keys():  height_to_widths[height].sort()

Step 3: Query Using Binary Search Template

For each point (x, y), we iterate through valid heights (y to 100) and count rectangles with width >= x.

Binary Search Template (first_true_index):

We find the first index where width >= pointX:

feasible(idx) = widths[idx] >= pointX

Pattern: false, false, ..., true, true, true

left, right = 0, len(widths) - 1 first_true_index = len(widths) # Default: no width >= pointX  while left <= right:  mid = (left + right) // 2  if widths[mid] >= pointX: # feasible  first_true_index = mid  right = mid - 1  else:  left = mid + 1  count = len(widths) - first_true_index

The count of rectangles with width >= pointX is len(widths) - first_true_index.

Time Complexity:

• Preprocessing: O(n log n) for sorting
• Per point query: O(h × log n) where h = 100 (max height)
• Total: O(n log n + m × h × log n)

Space Complexity: O(n) for storing grouped rectangles.

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]

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. Using Wrong Binary Search Template

The problem requires finding the first index where width >= pointX (first true pattern).

Wrong approach:

while left < right:  mid = (left + right) >> 1  if widths[mid] >= pointX:  right = mid  else:  left = mid + 1 return left # Returns left directly

Correct approach (first_true_index template):

first_true_index = len(widths) # Default while left <= right:  mid = (left + right) // 2  if widths[mid] >= pointX:  first_true_index = mid  right = mid - 1  else:  left = mid + 1 return first_true_index

2. Incorrect Default Value for first_true_index

When no width >= pointX exists, first_true_index should default to len(widths) so that count = len(widths) - first_true_index = 0.

Wrong: first_true_index = -1 (would give wrong count) Correct: first_true_index = len(widths)

3. Forgetting to Sort After Grouping

Binary search requires sorted data:

# Missing sort causes incorrect results! for height in height_to_widths.keys():  height_to_widths[height].sort() # Don't forget this!

4. Hardcoding Height Upper Bound

The code assumes heights ≤ 100 (LeetCode constraint). For robustness, calculate the actual max height:

max_height = max(h for _, h in rectangles) if rectangles else 0