Count Number of Rectangles Containing Each Point — Solution
Count Number of Rectangles Containing Each Point solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Number of Rectangles Containing Each Point is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each rectangles[i] = [l_i, h_i] is an axis-aligned rectangle with its bottom-left corner at the origin (0, 0) and its top-right corner at (l_i, h_i).
Each points[j] = [x_j, y_j] is a point. A rectangle contains a point when 0 <= x_j <= l_i and 0 <= y_j <= h_i — points on the edges count.
Return an array whose j-th entry is the number of rectangles that contain point j. Heights are small (at most 100) while lengths can be huge.
Example 1
Input: rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
Output: [2,1]
Explanation: Point (2, 1) lies in [2,3] and [2,5]; point (1, 4) only in [2,5].
Example 2
Input: rectangles = [[4,7],[9,2],[6,7]], points = [[5,7],[1,1],[10,1]]
Output: [1,3,0]
Constraints
1 <= rectangles.length, points.length <= 5 * 10^41 <= l_i, x_j <= 10^91 <= h_i, y_j <= 100All rectangles are distinct, and all points are distinct.
Hints for Count Number of Rectangles Containing Each Point
Hint 1
Heights only range over 1..100 — that is small enough to loop over.
Hint 2
Group the rectangles by height and sort each group's lengths.
Hint 3
For a point
(x, y), visit every heighth >= yand binary-search how many lengths in that group are>= x.
How to solve Count Number of Rectangles Containing Each Point
Exploit the tiny height range: bucket rectangle lengths by height, sort each bucket, and answer a point by summing, over the heights that are tall enough, how many lengths are long enough — a binary search per bucket.
Approach
- Create 101 buckets; put
l_iinto bucketh_ifor every rectangle. - Sort every bucket.
- For each point
(x, y), loophfromyto 100 and addbucket[h].length - lowerBound(bucket[h], x)(the lengths that are>= x). - Return the sums in point order.
Why it works
A rectangle contains (x, y) exactly when its height is at least y and its length is at least x. Bucketing by height enumerates the first condition directly, and inside a sorted bucket the lengths >= x form a suffix whose start is the lower bound of x.
Complexity
- Time —
O(R log R + P · 100 · log R) - Space —
O(R)
Pitfalls
- Containment includes the edges: use
>=for both coordinates. - Do not sort by length and loop over lengths — they go up to 10^9; it is the heights that are small.
- Answers must come back in the original point order.
Reference solution
Python
from typing import List
import bisect
def countRectangles(rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
buckets = [[] for _ in range(101)]
for l, h in rectangles:
buckets[h].append(l)
for b in buckets:
b.sort()
res = []
for x, y in points:
total = 0
for h in range(y, 101):
b = buckets[h]
if b:
total += len(b) - bisect.bisect_left(b, x)
res.append(total)
return resJava
public static int[] countRectangles(int[][] rectangles, int[][] points) {
List<List<Integer>> tmp = new ArrayList<>();
for (int h = 0; h <= 100; h++) tmp.add(new ArrayList<>());
for (int[] r : rectangles) tmp.get(r[1]).add(r[0]);
int[][] buckets = new int[101][];
for (int h = 0; h <= 100; h++) {
List<Integer> src = tmp.get(h);
buckets[h] = new int[src.size()];
for (int i = 0; i < src.size(); i++) buckets[h][i] = src.get(i);
Arrays.sort(buckets[h]);
}
int[] res = new int[points.length];
for (int j = 0; j < points.length; j++) {
int x = points[j][0], y = points[j][1], total = 0;
for (int h = y; h <= 100; h++) {
int[] b = buckets[h];
int lo = 0, hi = b.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (b[mid] < x) lo = mid + 1; else hi = mid;
}
total += b.length - lo;
}
res[j] = total;
}
return res;
}C++
vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
vector<vector<int>> buckets(101);
for (auto& r : rectangles) buckets[r[1]].push_back(r[0]);
for (auto& b : buckets) sort(b.begin(), b.end());
vector<int> res;
for (auto& p : points) {
int x = p[0], y = p[1], total = 0;
for (int h = y; h <= 100; h++) {
const vector<int>& b = buckets[h];
total += b.end() - lower_bound(b.begin(), b.end(), x);
}
res.push_back(total);
}
return res;
}JavaScript
var countRectangles = function(rectangles, points) {
var buckets = [];
for (var h = 0; h <= 100; h++) buckets.push([]);
for (var i = 0; i < rectangles.length; i++) buckets[rectangles[i][1]].push(rectangles[i][0]);
for (var h2 = 0; h2 <= 100; h2++) buckets[h2].sort(function(a, b) { return a - b; });
var res = [];
for (var j = 0; j < points.length; j++) {
var x = points[j][0], y = points[j][1], total = 0;
for (var hh = y; hh <= 100; hh++) {
var b = buckets[hh];
if (b.length === 0) continue;
var lo = 0, hi = b.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (b[mid] < x) lo = mid + 1; else hi = mid;
}
total += b.length - lo;
}
res.push(total);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets