Count Number of Rectangles Containing Each Point
MedPrompt
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 * 104rectangles[i].length == points[j].length == 21 <= li, xj <= 1091 <= hi, yj <= 100- All the
rectanglesare unique. - All the
pointsare 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
ansof the same size as thepointsarray, which will store the final counts. - Iterate through each point
(x, y)from thepointsarray at indexi. - For each point, initialize a counter
countto zero. - Iterate through every rectangle
(l, h)from therectanglesarray. - Check if the current point is contained in the current rectangle using the condition
x <= landy <= h. - If the condition is met, increment the
countfor the current point. - After checking all rectangles, store the final
countinans[i]. - Return the
ansarray.
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.
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.
Algorithm
- Create an array of lists,
heightsMap, of size 101 (since max height is 100). - Iterate through all rectangles
(l, h)and add the lengthlto the list atheightsMap[h]. - For each height
hfrom 1 to 100, sort the list of lengthsheightsMap[h]in ascending order. - Initialize an answer array
ans. - For each point
(x, y):- Initialize a counter
countto 0. - Iterate through all possible heights
h_ifromyto 100. - For each
h_i, perform a binary search on the sorted listheightsMap[h_i]to find the number of lengthsl >= x. - Add this number to the
count.
- Initialize a counter
- Store the final
countin theansarray for the current point.
Walkthrough
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).
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; }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
- Group rectangles by height into
heightsMap, whereheightsMap[h]contains a sorted list of lengths for rectangles of heighth. - Group points by y-coordinate into
queries, wherequeries[y]contains pairs of(x, original_index)for points at that y-coordinate. - Initialize an empty list
active_lengthsto store lengths of currently relevant rectangles. - Iterate with a sweep-line from
h = 100down to 1.- For each
h, add all lengths fromheightsMap[h]toactive_lengths. - Sort
active_lengthsto prepare for binary search. (This can be optimized by merging sorted lists). - Process all points with y-coordinate
hstored inqueries[h]. - For each such point
(x, original_index), binary search onactive_lengthsto find the count of lengths>= x. - Store this count in the answer array at
original_index.
- For each
Walkthrough
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.
-
Pre-processing: First, we group rectangles by height into an array of lists
heightsMap, whereheightsMap[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, wherequeries[y]stores pairs of(x, original_index)for all points with that y-coordinate. -
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 fromh = 100down to 1. -
Processing at each height
h:- We 'activate' all rectangles with height
hby adding their lengths fromheightsMap[h]into ouractive_lengthslist. - We then sort the
active_lengthslist. A more efficient way to do this is to merge the already sortedactive_lengthslist (from steph+1) with the sortedheightsMap[h]list, which takes linear time relative to the list sizes. - After updating
active_lengths, we process all the points that havey = h. For each such point(x, original_index)fromqueries[h], we perform a binary search on the currentactive_lengthslist to find the number of lengths>= x. This count is the answer for this point, which we store in our final answer array.
- We 'activate' all rectangles with height
By processing in this order, each rectangle's length is added to the active_lengths list only once, leading to significant performance gains.
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo 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.