Skip to content

2250. Count Number of Rectangles Containing Each Point

  • Time: $O(100\texttt{sort}) = O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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