Count Number of Rectangles Containing Each Point

Count Number of Rectangles Containing Each Point - Problem

You are given a 2D integer array rectangles where rectangles[i] = [li, hi] indicates that the i-th 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 i-th 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 j-th point.

The i-th rectangle contains the j-th 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.

Input & Output

Example 1 — Basic Rectangle Coverage

$ Input: rectangles = [[3,1],[1,1],[1,2]], points = [[1,1],[1,0]]

› Output: [3,2]

💡 Note: Point (1,1) is contained in all 3 rectangles: [3,1] (1≤3, 1≤1), [1,1] (1≤1, 1≤1), [1,2] (1≤1, 1≤2). Point (1,0) is contained in 2 rectangles: [3,1] (1≤3, 0≤1), [1,2] (1≤1, 0≤2), but not [1,1] since 0≤1 fails.

Example 2 — Edge and Corner Cases

$ Input: rectangles = [[1,1],[2,2],[3,3]], points = [[1,1],[2,2],[0,0]]

› Output: [1,2,3]

💡 Note: Point (1,1) fits in [1,1], (2,2) fits in [2,2] and [3,3], (0,0) fits in all rectangles as it's at the origin.

Example 3 — Outside All Rectangles

$ Input: rectangles = [[1,1],[2,2]], points = [[3,3],[4,4]]

› Output: [0,0]

💡 Note: Both points (3,3) and (4,4) are outside all rectangles, so count is 0 for each.

Constraints

1 ≤ rectangles.length ≤ 5 × 10⁴
rectangles[i].length == 2
1 ≤ l_i, h_i ≤ 10⁹
1 ≤ points.length ≤ 5 × 10⁴
points[j].length == 2
0 ≤ x_j, y_j ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Rectangles with dimensions and points to check

Check Containment

Determine which rectangles contain each point

Count Results

Return count array for each point

Key Takeaway

🎯 Key Insight: Since all rectangles are anchored at origin (0,0), containment is simply checking if point coordinates are within rectangle dimensions

Asked in

G Google 25 a Amazon 18 M Microsoft 12 f Facebook 10

Brief HTML summary: The key insight is that each rectangle is anchored at origin (0,0), so we only need to check if point coordinates are within the rectangle bounds. The brute force approach checks each point against all rectangles in O(n×m) time. Optimized approaches use sorting and binary search or coordinate compression for faster queries. Best approach depends on input size and query frequency. Time: O(n×m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Coordinate Compression	O(k² + n)	O(k²)	Compress coordinates and use 2D prefix sums for fast range queries
Brute Force	O(n×m)	O(1)	Check each point against every rectangle individually
Sorted Binary Search	O((m+n) log m)	O(m)	Sort rectangles by dimensions and use binary search for efficient lookups

Coordinate Compression — Algorithm Steps

Compress all x and y coordinates
Create 2D grid marking rectangle presence
Build 2D prefix sum array
Answer each point query in O(1) using prefix sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Compress Coordinates

Map all unique x,y values to smaller indices

Build 2D Grid

Create prefix sum array for rectangle counts

Query in O(1)

Answer point queries using precomputed sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int** rectangles, int rectanglesSize, int** points, int pointsSize, int* returnSize) {
    int* result = (int*)malloc(pointsSize * sizeof(int));
    *returnSize = pointsSize;
    
    for (int i = 0; i < pointsSize; i++) {
        int x = points[i][0];
        int y = points[i][1];
        
        if (x < 0 || y < 0) {
            result[i] = 0;
            continue;
        }
        
        int count = 0;
        for (int j = 0; j < rectanglesSize; j++) {
            if (x <= rectangles[j][0] && y <= rectangles[j][1]) {
                count++;
            }
        }
        
        result[i] = count;
    }
    
    return result;
}

int main() {
    int rectangles[][2] = {{3,1}, {1,1}, {1,2}};
    int points[][2] = {{1,1}, {1,0}};
    int* rect_ptrs[] = {rectangles[0], rectangles[1], rectangles[2]};
    int* point_ptrs[] = {points[0], points[1]};
    
    int returnSize;
    int* result = solution(rect_ptrs, 3, point_ptrs, 2, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k² + n)

k is unique coordinates, O(k²) to build 2D prefix array, O(n) for all queries

✓ Linear Growth

Space Complexity

O(k²)

2D prefix sum array of size k×k where k is unique coordinates

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Coordinate Compression — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler