Scale Engineer

Count Number of Rectangles Containing Each Point

Med
#2050Time: O(N * M), where N is the number of rectangles and M is the number of points. For each of the M points, we perform a scan of all N rectangles.Space: O(M), where M is the number of points. This space is primarily for the output array. If the output array is not considered, the extra space complexity is O(1).
Algorithms
Binary SearchSorting
Data structures
ArrayHash TableBinary Indexed Tree

Prompt

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).

The ith rectangle has its bottom-left corner point at the coordinates (0, 0) and its top-right corner point at (li, hi).

Return an integer array count of length points.length where count[j] is the number of rectangles that contain the jth point.

The ith rectangle contains the jth point if 0 <= xj <= li and 0 <= yj <= hi. Note that points that lie on the edges of a rectangle are also considered to be contained by that rectangle.

 

Example 1:

Input: rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
Output: [2,1]
Explanation: 
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]
Explanation:
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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. For every point, we iterate through every single rectangle and check if it contains the point. This is the most straightforward but also the least efficient way to solve the problem.

Algorithm

  • Initialize an integer array ans of the same size as the points array, which will store the final counts.
  • Iterate through each point (x, y) from the points array at index i.
  • For each point, initialize a counter count to zero.
  • Iterate through every rectangle (l, h) from the rectangles array.
  • Check if the current point is contained in the current rectangle using the condition x <= l and y <= h.
  • If the condition is met, increment the count for the current point.
  • After checking all rectangles, store the final count in ans[i].
  • Return the ans array.

Walkthrough

In this method, we use a nested loop structure. The outer loop iterates through each point for which we need to find the count. The inner loop iterates through all the available rectangles. Inside the inner loop, a simple conditional check points[j][0] <= rectangles[i][l] and points[j][1] <= rectangles[i][h] determines if the point lies within or on the boundary of the rectangle. If it does, we increment a counter for that specific point. After the inner loop completes, the counter holds the total number of rectangles containing the point, and this value is stored in our result array.

class Solution {    public int[] countRectangles(int[][] rectangles, int[][] points) {        int n = points.length;        int[] ans = new int[n];        for (int i = 0; i < n; i++) {            int x = points[i][0];            int y = points[i][1];            int count = 0;            for (int[] rect : rectangles) {                int l = rect[0];                int h = rect[1];                if (x <= l && y <= h) {                    count++;                }            }            ans[i] = count;        }        return ans;    }}

Complexity

Time

O(N * M), where N is the number of rectangles and M is the number of points. For each of the M points, we perform a scan of all N rectangles.

Space

O(M), where M is the number of points. This space is primarily for the output array. If the output array is not considered, the extra space complexity is O(1).

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal extra space.

Cons

  • Extremely inefficient for the given constraints.

  • Will result in a Time Limit Exceeded (TLE) error on competitive programming platforms.

Solutions

class Solution {public  int[] countRectangles(int[][] rectangles, int[][] points) {    int n = 101;    List<Integer>[] d = new List[n];    Arrays.setAll(d, k->new ArrayList<>());    for (int[] r : rectangles) {      d[r[1]].add(r[0]);    }    for (List<Integer> v : d) {      Collections.sort(v);    }    int m = points.length;    int[] ans = new int[m];    for (int i = 0; i < m; ++i) {      int x = points[i][0], y = points[i][1];      int cnt = 0;      for (int h = y; h < n; ++h) {        List<Integer> xs = d[h];        int left = 0, right = xs.size();        while (left < right) {          int mid = (left + right) >> 1;          if (xs.get(mid) >= x) {            right = mid;          } else {            left = mid + 1;          }        }        cnt += xs.size() - left;      }      ans[i] = cnt;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem