Count Number of Rectangles Containing Each Point

Medium
1382.

Count Number of Rectangles Containing Each Point

Count Number of Rectangles Containing Each Point is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

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^4
  • 1 <= l_i, x_j <= 10^9
  • 1 <= h_i, y_j <= 100
  • All rectangles are distinct, and all points are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} rectangles
 * @param {number[][]} points
 * @return {number[]}
 */
var countRectangles = function(rectangles, points) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • 1 <= l_i, x_j <= 10^9
  • 1 <= h_i, y_j <= 100
  • All rectangles are distinct, and all points are distinct.

Hints for Count Number of Rectangles Containing Each Point

  1. Hint 1

    Heights only range over 1..100 — that is small enough to loop over.

  2. Hint 2

    Group the rectangles by height and sort each group's lengths.

  3. Hint 3

    For a point (x, y), visit every height h >= y and 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

  1. Create 101 buckets; put l_i into bucket h_i for every rectangle.
  2. Sort every bucket.
  3. For each point (x, y), loop h from y to 100 and add bucket[h].length - lowerBound(bucket[h], x) (the lengths that are >= x).
  4. 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 res

Java

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