Count Number of Rectangles Containing Each Point solution and explanation
8 more videos on this problem
2250. Count Number of Rectangles Containing Each Point || Leetcode Weekly Contest 290 ||Bro Coders · 14:06 · 2K views
Count Number of Rectangles Containing Each Point | Leetcode 2250 | Maths | Contest 290 🔥🔥Coding Decoded · 9:53 · 2K views
2250. Count Number of Rectangles Containing Each Point (Leetcode Medium)Programming Live with Larry · 29:17 · 852 views
Weekly Leetcode Contest 290 | 6043. Count Number of Rectangles Containing Each PointcodingMohan · 13:44 · 812 views
【每日一题】LeetCode 2250. Count Number of Rectangles Containing Each PointHuifeng Guan · 23:11 · 504 views
Count Number of Rectangles Containing Each Point | Leetcode Weekly 290 - Hitesh TripathiCoding Talkies | Newton School · 23:18 · 474 views
Leetcode Weekly-contest-290 - Count Number of Rectangles Containing Each PointPrakhar Agrawal · 16:00 · 234 views
LeetCode 2250 count number of rectangles containing each point[CE] Code Engineering · 28:15 · 90 views
Leetcode 2250. Count Number of Rectangles Containing Each PointYou Wu · 31:03 · 41 views
The 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:
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.
Approach overview
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.
Approach 1: Brute Force Approach
This approach involves checking each point against all rectangles to see if the rectangle contains the point.
def countRectangles(rectangles, points):
result = [0] * len(points)
for i, (x, y) in enumerate(points):
for lx, hy in rectangles:
if x <= lx and y <= hy:
result[i] += 1
return result
rectangles = [[1, 2], [2, 3], [2, 5]]
points = [[2, 1], [1, 4]]
print(countRectangles(rectangles, points))import java.util.Arrays;
public class Solution {
public int[] countRectangles(int[][] rectangles, int[][] points) {
int[] result = new int[points.length];
for (int i = 0; i < points.length; i++) {
for (int[] rectangle : rectangles) {
if (points[i][0] <= rectangle[0] && points[i][1] <= rectangle[1]) {
result[i]++;
}
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] rectangles = {{1, 2}, {2, 3}, {2, 5}};
int[][] points = {{2, 1}, {1, 4}};
System.out.println(Arrays.toString(sol.countRectangles(rectangles, points)));
}
}#include <vector>
#include <iostream>
std::vector<int> countRectangles(std::vector<std::vector<int>>& rectangles, std::vector<std::vector<int>>& points) {
std::vector<int> count(points.size(), 0);
for (int i = 0; i < points.size(); ++i) {
for (int j = 0; j < rectangles.size(); ++j) {
if (points[i][0] <= rectangles[j][0] && points[i][1] <= rectangles[j][1]) {
count[i]++;
}
}
}
return count;
}
int main() {
std::vector<std::vector<int>> rectangles = {{1, 2}, {2, 3}, {2, 5}};
std::vector<std::vector<int>> points = {{2, 1}, {1, 4}};
std::vector<int> results = countRectangles(rectangles, points);
for (int count : results) {
std::cout << count << " ";
}
return 0;
}function countRectangles(rectangles, points) {
const result = new Array(points.length).fill(0);
points.forEach((point, i) => {
rectangles.forEach(([l, h]) => {
if (point[0] <= l && point[1] <= h) {
result[i] += 1;
}
});
});
return result;
}
const rectangles = [[1, 2], [2, 3], [2, 5]];
const points = [[2, 1], [1, 4]];
console.log(countRectangles(rectangles, points));#include <stdio.h>
int* countRectangles(int rectangles[][2], int rectanglesSize, int points[][2], int pointsSize, int* returnSize) {
*returnSize = pointsSize;
static int count[50000];
for (int i = 0; i < pointsSize; ++i) {
count[i] = 0;
for (int j = 0; j < rectanglesSize; ++j) {
if (points[i][0] <= rectangles[j][0] && points[i][1] <= rectangles[j][1]) {
count[i]++;
}
}
}
return count;
}
int main() {
int rectangles[][2] = {{1, 2}, {2, 3}, {2, 5}};
int points[][2] = {{2, 1}, {1, 4}};
int returnSize;
int *result = countRectangles(rectangles, 3, points, 2, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
return 0;
}using System;
class Solution {
public int[] CountRectangles(int[][] rectangles, int[][] points) {
int[] result = new int[points.Length];
for (int i = 0; i < points.Length; i++) {
int x = points[i][0], y = points[i][1];
foreach (var rectangle in rectangles) {
if (x <= rectangle[0] && y <= rectangle[1]) {
result[i]++;
}
}
}
return result;
}
static void Main() {
var sol = new Solution();
int[][] rectangles = new int[][] { new int[] { 1, 2 }, new int[] { 2, 3 }, new int[] { 2, 5 } };
int[][] points = new int[][] { new int[] { 2, 1 }, new int[] { 1, 4 } };
Console.WriteLine(string.Join(", ", sol.CountRectangles(rectangles, points)));
}
}This Python implementation initializes a list to store counts of how many rectangles each point is contained in. It checks each rectangle if it contains the current point by comparing the point's coordinates against the rectangle's dimensions.
Time Complexity: O(m * n). Space Complexity: O(m).
Approach 2: Optimized with Sorting and Binary Search
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.
from bisect import bisect_left
def countRectangles(rectangles, points):
rectangles.sort()
result = [0] * len(points)
for i, (x, y) in enumerate(points):
idx = bisect_left(rectangles, [x, 0])
count = 0
for j in range(idx, len(rectangles)):
if rectangles[j][1] >= y:
count += 1
result[i] = count
return result
rectangles = [[1, 2], [2, 3], [2, 5]]
points = [[2, 1], [1, 4]]
print(countRectangles(rectangles, points))import java.util.Arrays;
public class Solution {
private int countWithBinarySearch(int[][] rectangles, int x, int y) {
int low = 0, high = rectangles.length, mid;
while (low < high) {
mid = low + (high - low) / 2;
if (rectangles[mid][0] < x) low = mid + 1;
else high = mid;
}
int count = 0;
for (int i = low; i < rectangles.length; i++) {
if (rectangles[i][1] >= y) count++;
}
return count;
}
public int[] countRectangles(int[][] rectangles, int[][] points) {
int[] result = new int[points.length];
Arrays.sort(rectangles, java.util.Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < points.length; i++) {
result[i] = countWithBinarySearch(rectangles, points[i][0], points[i][1]);
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] rectangles = {{1, 2}, {2, 3}, {2, 5}};
int[][] points = {{2, 1}, {1, 4}};
System.out.println(Arrays.toString(sol.countRectangles(rectangles, points)));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int countWithBinarySearch(const std::vector<std::vector<int>>& rectangles, int x, int y) {
int lo = 0, hi = rectangles.size(), mid;
while (lo < hi) {
mid = lo + (hi - lo) / 2;
if (rectangles[mid][0] < x) lo = mid + 1;
else hi = mid;
}
int count = 0;
for (int i = lo; i < rectangles.size(); ++i) {
if (rectangles[i][1] >= y) count++;
}
return count;
}
std::vector<int> countRectangles(std::vector<std::vector<int>>& rectangles, std::vector<std::vector<int>>& points) {
std::vector<int> result(points.size(), 0);
std::sort(rectangles.begin(), rectangles.end());
for (int i = 0; i < points.size(); ++i) {
result[i] = countWithBinarySearch(rectangles, points[i][0], points[i][1]);
}
return result;
}
int main() {
std::vector<std::vector<int>> rectangles = {{1, 2}, {2, 3}, {2, 5}};
std::vector<std::vector<int>> points = {{2, 1}, {1, 4}};
std::vector<int> results = countRectangles(rectangles, points);
for (int count : results) {
std::cout << count << " ";
}
return 0;
}function countRectangles(rectangles, points) {
rectangles.sort((a, b) => a[0] - b[0]);
const result = Array(points.length).fill(0);
points.forEach(([x, y], i) => {
let idx = 0;
while (idx < rectangles.length && rectangles[idx][0] < x) idx++;
for (let j = idx; j < rectangles.length; j++) {
if (rectangles[j][1] >= y) {
result[i]++;
}
}
});
return result;
}
const rectangles = [[1, 2], [2, 3], [2, 5]];
const points = [[2, 1], [1, 4]];
console.log(countRectangles(rectangles, points));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int **)a)[0] - (*(int **)b)[0];
}
int countWithBinarySearch(int rectangles[][2], int rectanglesSize, int x, int y) {
int low = 0, high = rectanglesSize - 1, mid;
while (low <= high) {
mid = low + (high - low) / 2;
if (rectangles[mid][0] >= x)
high = mid - 1;
else
low = mid + 1;
}
int count = 0;
for (int i = low; i < rectanglesSize; i++) {
if (rectangles[i][1] >= y) count++;
}
return count;
}
int* countRectangles(int rectangles[][2], int rectanglesSize, int points[][2], int pointsSize, int* returnSize) {
*returnSize = pointsSize;
static int count[50000];
qsort(rectangles, rectanglesSize, sizeof(rectangles[0]), compare);
for (int i = 0; i < pointsSize; ++i) {
count[i] = countWithBinarySearch(rectangles, rectanglesSize, points[i][0], points[i][1]);
}
return count;
}
int main() {
int rectangles[][2] = {{1, 2}, {2, 3}, {2, 5}};
int points[][2] = {{2, 1}, {1, 4}};
int returnSize;
int *result = countRectangles(rectangles, 3, points, 2, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
return 0;
}using System;
using System.Linq;
public class Solution {
private int CountWithBinarySearch(int[][] rectangles, int x, int y) {
int low = Array.BinarySearch(rectangles, new int[] { x, 0 }, Comparer<int[]>.Create((a, b) => a[0].CompareTo(b[0])));
if (low < 0) low = ~low;
int count = 0;
for (int i = low; i < rectangles.Length; i++) {
if (rectangles[i][1] >= y) count++;
}
return count;
}
public int[] CountRectangles(int[][] rectangles, int[][] points) {
Array.Sort(rectangles, (a, b) => a[0].CompareTo(b[0]));
int[] result = new int[points.Length];
for (int i = 0; i < points.Length; i++) {
result[i] = CountWithBinarySearch(rectangles, points[i][0], points[i][1]);
}
return result;
}
public static void Main() {
var sol = new Solution();
int[][] rectangles = new int[][] { new int[] { 1, 2 }, new int[] { 2, 3 }, new int[] { 2, 5 } };
int[][] points = new int[][] { new int[] { 2, 1 }, new int[] { 1, 4 } };
Console.WriteLine(string.Join(", ", sol.CountRectangles(rectangles, points)));
}
}In this Python implementation, the rectangles are sorted first. For each point, a binary search determines the starting point to check rectangles based on x-coordinates, followed by filtering using y-coordinates.
Time Complexity: O(n log n + m log n). Space Complexity: O(1).
Approach 3: Default Approach
function countRectangles(rectangles: number[][], points: number[][]): number[] {
const n = 101;
let ymap = Array.from({ length: n }, v => []);
for (let [x, y] of rectangles) {
ymap[y].push(x);
}
for (let nums of ymap) {
nums.sort((a, b) => a - b);
}
let ans = [];
for (let [x, y] of points) {
let count = 0;
for (let h = y; h < n; h++) {
const nums = ymap[h];
let left = 0,
right = nums.length;
while (left < right) {
let mid = (left + right) >> 1;
if (x > nums[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
count += nums.length - right;
}
ans.push(count);
}
return ans;
}func countRectangles(rectangles [][]int, points [][]int) []int {
n := 101
d := make([][]int, 101)
for _, r := range rectangles {
d[r[1]] = append(d[r[1]], r[0])
}
for _, v := range d {
sort.Ints(v)
}
var ans []int
for _, p := range points {
x, y := p[0], p[1]
cnt := 0
for h := y; h < n; h++ {
xs := d[h]
left, right := 0, len(xs)
for left < right {
mid := (left + right) >> 1
if xs[mid] >= x {
right = mid
} else {
left = mid + 1
}
}
cnt += len(xs) - left
}
ans = append(ans, cnt)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(m * n). Space Complexity: O(m). |
| Optimized with Sorting and Binary Search | Time Complexity: O(n log n + m log n). Space Complexity: O(1). |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count Number of Rectangles Containing Each Point easy or hard?
The problem is rated Medium on LeetCode. The brute force logic is straightforward, but recognizing that heights are bounded and that queries can be answered using sorted width lists with binary search requires stronger algorithmic insight.
Count Number of Rectangles Containing Each Point Python/Java solution
In Python or Java, the optimized solution builds lists of widths grouped by rectangle height, sorts each list, and uses binary search (bisect in Python or Collections.binarySearch in Java) to count widths ≥ x for each query point. This keeps query time logarithmic and handles up to tens of thousands of rectangles efficiently.
How to solve Count Number of Rectangles Containing Each Point in O(n)?
A near-linear approach uses height bucketing because rectangle heights are bounded (≤100). Store rectangle widths for each height and sort them. For each point, scan the relevant height buckets and use binary search to count valid widths. The preprocessing is O(R log R) and each query performs a small number of logarithmic searches.
What is the best approach for Count Number of Rectangles Containing Each Point?
The most practical approach groups rectangles by height and sorts their widths. For each query point (x, y), you only consider rectangles with height ≥ y and use binary search to count widths ≥ x. This reduces the complexity to roughly O((R + P) log R) and avoids scanning all rectangles for every query.
Is Count Number of Rectangles Containing Each Point asked at Google/Amazon/Meta?
Problems combining geometric conditions with binary search and preprocessing frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test your ability to convert brute force comparisons into efficient query structures using sorting, indexing, or Fenwick trees.
What data structure is used in Count Number of Rectangles Containing Each Point?
Common solutions use arrays for height buckets and binary search over sorted width lists. Some advanced implementations process points offline with a Binary Indexed Tree (Fenwick Tree) to support fast prefix queries while iterating rectangles in sorted order.
What is the time complexity of Count Number of Rectangles Containing Each Point?
The brute force solution runs in O(R × P) time because every point checks every rectangle. The optimized approach using sorting and binary search processes rectangles once and answers each query with logarithmic lookups, resulting in about O((R + P) log R) time and O(R) extra space.