2250. Count Number of Rectangles Containing Each Point LeetCode Solution

In this guide, you will get 2250. Count Number of Rectangles Containing Each Point LeetCode Solution with the best time and space complexity. The solution to Count Number of Rectangles Containing Each Point problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Number of Rectangles Containing Each Point solution in C++
Count Number of Rectangles Containing Each Point solution in Java
Count Number of Rectangles Containing Each Point solution in Python
Additional Resources

2250. Count Number of Rectangles Containing Each Point LeetCode Solution image

Problem Statement of Count Number of Rectangles Containing Each Point

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.

Complexity Analysis

Time Complexity: O(100\texttt{sort}) = O(\texttt{sort})
Space Complexity: O(n)

2250. Count Number of Rectangles Containing Each Point LeetCode Solution in C++

class Solution {
 public:
  vector<int> countRectangles(vector<vector<int>>& rectangles,
                              vector<vector<int>>& points) {
    vector<int> ans;
    vector<vector<int>> yToXs(101);

    for (const vector<int>& r : rectangles)
      yToXs[r[1]].push_back(r[0]);

    for (auto& xs : yToXs)
      ranges::sort(xs);

    for (const vector<int>& p : points) {
      int count = 0;
      for (int y = p[1]; y < 101; ++y) {
        const vector<int>& xs = yToXs[y];
        count += xs.end() - ranges::lower_bound(xs, p[0]);
      }
      ans.push_back(count);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2250. Count Number of Rectangles Containing Each Point LeetCode Solution in Java

class Solution {
  public int[] countRectangles(int[][] rectangles, int[][] points) {
    int[] ans = new int[points.length];
    List<Integer>[] yToXs = new List[101];

    for (int i = 0; i < 101; ++i)
      yToXs[i] = new ArrayList<>();

    for (int[] r : rectangles)
      yToXs[r[1]].add(r[0]);

    for (List<Integer> xs : yToXs)
      Collections.sort(xs);

    for (int i = 0; i < points.length; ++i) {
      int count = 0;
      for (int y = points[i][1]; y < 101; ++y) {
        List<Integer> xs = yToXs[y];
        count += xs.size() - firstGreaterEqual(xs, points[i][0]);
      }
      ans[i] = count;
    }

    return ans;
  }

  private int firstGreaterEqual(List<Integer> indices, int target) {
    final int i = Collections.binarySearch(indices, target);
    return i < 0 ? -i - 1 : i;
  }
}
// code provided by PROGIEZ

2250. Count Number of Rectangles Containing Each Point LeetCode Solution in Python

class Solution:
  def countRectangles(
      self,
      rectangles: list[list[int]],
      points: list[list[int]],
  ) -> list[int]:
    ans = []
    yToXs = [[] for _ in range(101)]

    for l, h in rectangles:
      yToXs[h].append(l)

    for xs in yToXs:
      xs.sort()

    for xi, yi in points:
      count = 0
      for y in range(yi, 101):
        xs = yToXs[y]
        count += len(xs) - bisect.bisect_left(xs, xi)
      ans.append(count)

    return ans
 # code by PROGIEZ