Count Number of Rectangles Containing Each Point

Count Number of Rectangles Containing Each Point

What is this problem about?

You are given a set of rectangles, each defined by its width $l$ and height $h$. You are also given a set of points. For each point $(x, y)$, you need to count how many rectangles cover it. A rectangle $(l, h)$ covers a point $(x, y)$ if $0 \le x \le l$ and $0 \le y \le h$.

Why is this asked in interviews?

This problem is asked by Meta and Amazon to test a candidate's ability to use sorting and binary search to optimize a multi-dimensional search problem. The key insight is that the height $h$ is typically constrained to a small range (e.g., 1 to 100), while the width and number of points can be large. This constraint allows for a hybrid approach.

Algorithmic pattern used

This is a Binary Search and Sorting problem.

1. Group rectangles by their heights. For each height from 1 to 100, maintain a sorted list of the widths of rectangles having that height.
2. For each point $(x, y)$:
   • Iterate through all possible rectangle heights $h$ that are $\ge y$.
   • In each list of widths for height $h$, use binary search (bisect_left or lower_bound) to find how many widths are $\ge x$.
   • Sum these counts together.

Example explanation

Rectangles: (5, 2), (10, 2), (10, 5). Point: (6, 2).

• Height 2 widths: [5, 10]. Binary search for $\ge 6$: only 1 width (10). Count = 1.
• Height 5 widths: [10]. Binary search for $\ge 6$: 1 width (10). Count = 1.
• Heights 1, 3, 4: No rectangles or height too small. Total count for point: 2.

Common mistakes candidates make

The most common mistake is treating it as a pure 2D geometry problem and trying to use a 2D Segment Tree or Fenwick Tree, which is overkill and hard to implement. Another mistake is ignoring the height constraint and trying to sort everything by width, which doesn't simplify the height check. Failing to sort the widths for binary search is also a frequent bug.

Interview preparation tip

Look for small constraints! If one dimension of a 2D problem is very small (like height $\le 100$), you can often use a simple loop over that dimension and optimize the other dimension with a standard 1D algorithm like binary search.