# Count Number of Rectangles Containing Each Point
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-rectangles-containing-each-point)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-rectangles-containing-each-point
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Binary Indexed Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-number-of-rectangles-containing-each-point/image0.png) 

**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:**

![](https://assets.glich.co/dsa/count-number-of-rectangles-containing-each-point/image1.png) 

**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
## Brute Force Iteration
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Grouping by Height with Binary Search
This approach improves upon the brute-force method by pre-processing the rectangles. The key observation is that the heights and y-coordinates are limited to a small range (1-100). We can leverage this by grouping rectangles by their height. For any given point `(x, y)`, we only need to consider rectangles with height `h >= y`. By pre-sorting the lengths of rectangles within each height group, we can use binary search to quickly count the valid rectangles.
**Time:** O(N log N + M * H_max * log N), where N is number of rectangles, M is number of points, and H_max is the maximum height (100). The `N log N` term is for sorting lengths within each height group (worst-case), and `M * H_max * log N` is for querying all points. · **Space:** O(N), where N is the number of rectangles, to store the `heightsMap`.
**Pros:** Significantly faster than brute force.; Effectively uses the constraint on the maximum height.
**Cons:** The query time for each point depends on its y-coordinate, making it slower for points with small y values.; It still involves multiple iterations and binary searches for a single point.
### Explanation
First, we pre-process the rectangles. We create an array of lists, `heightsMap`, of size 101. `heightsMap[h]` will store all the lengths `l` of rectangles that have height `h`. We iterate through the `rectangles` array, and for each rectangle `(l, h)`, we add `l` to the list at `heightsMap[h]`. To enable efficient searching, we sort the list of lengths for each height in ascending order.

Now, we process the points. For each point `(x, y)`, we need to find rectangles `(l, h)` where `l >= x` and `h >= y`. We iterate through all possible heights from `y` up to 100. For each such height `h_i`, we look at the corresponding list of lengths `heightsMap[h_i]`. In this list, we need to find how many lengths are greater than or equal to `x`. Since the list is sorted, we can use binary search to find the index of the first length that is `>= x`. The number of valid lengths for this height `h_i` is `(total lengths in the list) - (the found index)`. We sum up these counts for all heights from `y` to 100 to get the total count for the point `(x, y)`.

```java
import java.util.*;

class Solution {
    public int[] countRectangles(int[][] rectangles, int[][] points) {
        List<Integer>[] heightsMap = new ArrayList[101];
        for (int i = 0; i <= 100; i++) {
            heightsMap[i] = new ArrayList<>();
        }

        for (int[] rect : rectangles) {
            int l = rect[0];
            int h = rect[1];
            heightsMap[h].add(l);
        }

        for (int i = 0; i <= 100; i++) {
            Collections.sort(heightsMap[i]);
        }

        int[] ans = new int[points.length];
        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            int count = 0;
            for (int h = y; h <= 100; h++) {
                List<Integer> lengths = heightsMap[h];
                int low = 0, high = lengths.size() - 1;
                int firstIndex = lengths.size();
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (lengths.get(mid) >= x) {
                        firstIndex = mid;
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                count += lengths.size() - firstIndex;
            }
            ans[i] = count;
        }
        return ans;
    }
}
```
### Algorithm
- Create an array of lists, `heightsMap`, of size 101 (since max height is 100).
- Iterate through all rectangles `(l, h)` and add the length `l` to the list at `heightsMap[h]`.
- For each height `h` from 1 to 100, sort the list of lengths `heightsMap[h]` in ascending order.
- Initialize an answer array `ans`.
- For each point `(x, y)`:
  - Initialize a counter `count` to 0.
  - Iterate through all possible heights `h_i` from `y` to 100.
  - For each `h_i`, perform a binary search on the sorted list `heightsMap[h_i]` to find the number of lengths `l >= x`.
  - Add this number to the `count`.
- Store the final `count` in the `ans` array for the current point.

## Optimized Sweep-line by Y-coordinate
This is the most optimal approach, which uses a sweep-line algorithm. Instead of processing points independently, we process them in a specific order (by decreasing y-coordinate) to reuse computations. As we 'sweep' from the maximum height downwards, we incrementally add rectangles to an 'active' set. For any point at a certain y-level, we only need to search within this active set, which contains all rectangles tall enough to contain it.
**Time:** O(N log N + M + H_max * N log N). The `N log N` is for initial sorting. The `H_max * N log N` term comes from re-sorting the `active_lengths` list up to `H_max` times. With a merge optimization, this can be improved to O(N log N + M log N + H_max * N). · **Space:** O(N + M), where N is the number of rectangles and M is the number of points. This space is for storing `heightsMap`, `queries`, and `active_lengths`.
**Pros:** Highly efficient and optimal for the given constraints.; Avoids re-computation by processing points and rectangles in a coordinated manner.
**Cons:** More complex to implement correctly compared to other approaches.; Requires more space to store grouped points and active lengths.
### Explanation
The core idea is to process points from top to bottom (decreasing y-coordinate). As we sweep downwards, more rectangles become eligible to contain points.

1.  **Pre-processing:** First, we group rectangles by height into an array of lists `heightsMap`, where `heightsMap[h]` stores a list of lengths. We sort each of these length lists. We also group the points by their y-coordinate into another array of lists, `queries`, where `queries[y]` stores pairs of `(x, original_index)` for all points with that y-coordinate.

2.  **Sweep-line:** We initialize an empty list, `active_lengths`, which will store the lengths of all rectangles whose height is greater than or equal to the current y-coordinate we are processing. We then iterate with a sweep-line from `h = 100` down to 1.

3.  **Processing at each height `h`:**
    - We 'activate' all rectangles with height `h` by adding their lengths from `heightsMap[h]` into our `active_lengths` list.
    - We then sort the `active_lengths` list. A more efficient way to do this is to merge the already sorted `active_lengths` list (from step `h+1`) with the sorted `heightsMap[h]` list, which takes linear time relative to the list sizes.
    - After updating `active_lengths`, we process all the points that have `y = h`. For each such point `(x, original_index)` from `queries[h]`, we perform a binary search on the current `active_lengths` list to find the number of lengths `>= x`. This count is the answer for this point, which we store in our final answer array.

By processing in this order, each rectangle's length is added to the `active_lengths` list only once, leading to significant performance gains.

```java
import java.util.*;

class Solution {
    public int[] countRectangles(int[][] rectangles, int[][] points) {
        List<Integer>[] heightsMap = new ArrayList[101];
        for (int i = 0; i <= 100; i++) {
            heightsMap[i] = new ArrayList<>();
        }
        for (int[] rect : rectangles) {
            heightsMap[rect[1]].add(rect[0]);
        }

        for (int i = 0; i <= 100; i++) {
            Collections.sort(heightsMap[i]);
        }

        List<int[]>[] queries = new ArrayList[101];
        for (int i = 0; i <= 100; i++) {
            queries[i] = new ArrayList<>();
        }
        for (int i = 0; i < points.length; i++) {
            queries[points[i][1]].add(new int[]{points[i][0], i});
        }

        int[] ans = new int[points.length];
        List<Integer> activeLengths = new ArrayList<>();

        for (int h = 100; h >= 1; h--) {
            activeLengths.addAll(heightsMap[h]);
            Collections.sort(activeLengths); // Can be optimized with a merge operation

            if (!queries[h].isEmpty()) {
                for (int[] query : queries[h]) {
                    int x = query[0];
                    int originalIndex = query[1];
                    
                    int low = 0, high = activeLengths.size() - 1;
                    int firstIndex = activeLengths.size();
                    while (low <= high) {
                        int mid = low + (high - low) / 2;
                        if (activeLengths.get(mid) >= x) {
                            firstIndex = mid;
                            high = mid - 1;
                        } else {
                            low = mid + 1;
                        }
                    }
                    ans[originalIndex] = activeLengths.size() - firstIndex;
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Group rectangles by height into `heightsMap`, where `heightsMap[h]` contains a sorted list of lengths for rectangles of height `h`.
- Group points by y-coordinate into `queries`, where `queries[y]` contains pairs of `(x, original_index)` for points at that y-coordinate.
- Initialize an empty list `active_lengths` to store lengths of currently relevant rectangles.
- Iterate with a sweep-line from `h = 100` down to 1.
  - For each `h`, add all lengths from `heightsMap[h]` to `active_lengths`.
  - Sort `active_lengths` to prepare for binary search. (This can be optimized by merging sorted lists).
  - Process all points with y-coordinate `h` stored in `queries[h]`.
  - For each such point `(x, original_index)`, binary search on `active_lengths` to find the count of lengths `>= x`.
  - Store this count in the answer array at `original_index`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> countRectangles(vector<vector<int>> &rectangles,
                              vector<vector<int>> &points) {
    int n = 101;
    vector<vector<int>> d(n);
    for (auto &r : rectangles)
      d[r[1]].push_back(r[0]);
    for (auto &v : d)
      sort(v.begin(), v.end());
    vector<int> ans;
    for (auto &p : points) {
      int x = p[0], y = p[1];
      int cnt = 0;
      for (int h = y; h < n; ++h) {
        auto &xs = d[h];
        cnt += xs.size() - (lower_bound(xs.begin(), xs.end(), x) - xs.begin());
      }
      ans.push_back(cnt);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]: d = defaultdict(list) for x, y in rectangles: d[y]. append(x) for y in d . keys(): d[y]. sort() 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) return ans

```