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 <= 100rectangles are unique.points are unique.Problem Overview: You are given axis-aligned rectangles whose bottom-left corner is fixed at (0,0). Each rectangle is defined by its width l and height h. For every query point (x, y), count how many rectangles contain that point. A rectangle contains the point if l ≥ x and h ≥ y.
Approach 1: Brute Force Check (O(R * P) time, O(1) space)
The direct solution checks every rectangle for every point. For each query point, iterate through the list of rectangles and test whether the rectangle’s width and height satisfy l ≥ x and h ≥ y. If both conditions hold, increment the count for that point.
This approach relies only on simple array traversal and conditional checks. It is easy to implement and useful for verifying correctness on small inputs. The downside is the nested iteration: if there are R rectangles and P points, the algorithm performs R × P comparisons, which becomes too slow for large datasets.
Approach 2: Sorting + Binary Search (O((R + P) log R) time, O(R) space)
A key constraint in the problem is that rectangle heights are bounded (≤100). This allows grouping rectangles by their height. Create buckets where each index represents a height and store all rectangle widths with that height. Sort the widths in each bucket using sorting.
For a query point (x, y), only rectangles with height ≥ y can contain the point. Iterate through all height buckets from y up to the maximum height. For each bucket, use binary search to count how many stored widths are ≥ x. Because the widths are sorted, a single lower-bound search gives the count in O(log n).
This significantly reduces the work per query. Instead of scanning every rectangle, the algorithm performs a small number of binary searches over sorted lists. The preprocessing step sorts the widths once, and queries become fast lookups.
Recommended for interviews: Interviewers expect the optimized grouping with sorting and binary search. Starting with the brute force approach shows you understand the containment condition. Moving to height bucketing and binary search demonstrates algorithmic optimization and familiarity with common patterns in array processing and query acceleration. Some advanced variants also use a Binary Indexed Tree to process points offline, but the bucket + binary search approach is usually the cleanest solution.
This approach involves checking each point against all rectangles to see if the rectangle contains the point.
This C solution initializes an integer array 'count' to keep track of the rectangles containing each point. It iterates through each point and for each point, goes through all the rectangles to check containment. The result is returned as an array of counts.
Time Complexity: O(m * n), where m is the number of points and n is the number of rectangles. Space Complexity: O(m) for the array to store counts.
To improve efficiency, sort the rectangles by their length. For each point, count only rectangles whose lengths are greater than or equal to the point's x-coordinate by leveraging binary search, reducing the number of rectangles checked for y-coordinate condition.
This C solution sorts rectangles by length. For each point, binary search finds the starting index of possible candidate rectangles; a subsequent linear scan ensures only the matching rectangles are counted.
Time Complexity: O(n log n + m log n). Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(m * n), where m is the number of points and n is the number of rectangles. Space Complexity: O(m) for the array to store counts. |
| Optimized with Sorting and Binary Search | Time Complexity: O(n log n + m log n). Space Complexity: O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Rectangle Check | O(R × P) | O(1) | Small input sizes or for validating correctness before optimizing |
| Sorting + Binary Search with Height Buckets | O((R + P) log R) | O(R) | Large inputs with many queries; efficient when rectangle heights are bounded |
2250. Count Number of Rectangles Containing Each Point || Leetcode Weekly Contest 290 || • Bro Coders • 2,873 views views
Watch 9 more video solutions →Practice Count Number of Rectangles Containing Each Point with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor