LeetCode 2250 - Count Number of Rectangles Containing Each Point

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Binary Indexed Tree, Sorting

Solution

Here is the complete, detailed technical solution guide for LeetCode 2250 - Count Number of Rectangles Containing Each Point in a single, comprehensive response.

Problem Understanding

The problem provides two arrays: rectangles and points. Each element of rectangles is [li, hi], representing a rectangle with its bottom-left corner at (0, 0) and top-right corner at (li, hi). Each element of points is [xj, yj], representing a point in the 2D plane. The goal is to count, for each point, how many rectangles contain it. A point is considered inside a rectangle if it lies within or on the edges of the rectangle, meaning 0 <= xj <= li and 0 <= yj <= hi.

The input constraints are important: up to 5 * 10^4 rectangles and points, rectangle widths and point x-coordinates up to 10^9, and rectangle heights and point y-coordinates up to 100. The small maximum height (hi <= 100) suggests an opportunity to optimize by grouping rectangles by height. Rectangles and points are unique, which avoids duplicate counting issues. Edge cases include points lying exactly on rectangle edges and points or rectangles with minimum or maximum allowed dimensions.

The expected output is an array of integers where each element corresponds to a point in points and indicates the count of rectangles containing that point.

Approaches

Brute Force

The brute-force approach iterates through every rectangle for every point, checking if the point lies within the rectangle using the containment condition 0 <= xj <= li and 0 <= yj <= hi. This is correct but inefficient because it requires O(N * M) time where N = len(rectangles) and M = len(points). With the upper bound of 5 * 10^4 for both arrays, this approach can result in up to 2.5 billion operations, which is too slow.

Optimal Approach

The key observation is that rectangle heights are bounded (hi <= 100). We can group rectangles by height and sort the widths for each height group. Then, for a given point (xj, yj), only heights hi >= yj are relevant. Using binary search on the sorted widths in these height groups, we can count how many rectangles have li >= xj. This reduces the time complexity significantly.

The algorithm leverages two optimizations: height bucketing and binary search within sorted width lists.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N * M)	O(1)	Simple containment check for each point-rectangle pair
Optimal	O(N + M * H * log N)	O(N + H)	H = 100, group by height, binary search widths

Algorithm Walkthrough

Initialize a hash map (or list) height_to_widths where each key is a rectangle height and the value is a list of widths of rectangles with that height.
Populate height_to_widths by iterating through rectangles and appending each rectangle's width to the corresponding height list.
Sort each list of widths in ascending order. This allows efficient binary search for widths later.
Initialize an empty list result to store counts for each point.
For each point (xj, yj), initialize a counter count = 0.
Iterate through heights from yj up to the maximum possible height (100). For each height:

Retrieve the sorted list of widths widths.
Use binary search to find the index of the first width >= xj.
Add the number of widths from that index to the end of the list to count.

Append count to result.
Return result.

Why it works: By grouping rectangles by height and sorting widths, we efficiently check only rectangles that can potentially contain a point. Binary search ensures we count widths >= xj quickly. Since heights are bounded by 100, iterating over relevant heights is acceptable.

Python Solution

from typing import List
import bisect

class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        # Step 1: Group rectangles by height
        height_to_widths = [[] for _ in range(101)]  # Heights 1 to 100
        for li, hi in rectangles:
            height_to_widths[hi].append(li)
        
        # Step 2: Sort widths in each height group
        for h in range(1, 101):
            height_to_widths[h].sort()
        
        result = []
        
        # Step 3: For each point, count rectangles containing it
        for xj, yj in points:
            count = 0
            for h in range(yj, 101):
                widths = height_to_widths[h]
                # Binary search for first width >= xj
                idx = bisect.bisect_left(widths, xj)
                count += len(widths) - idx
            result.append(count)
        
        return result

Explanation: We create a list of lists to group rectangle widths by their height. Sorting each list allows fast binary search. For each point, we iterate through all heights >= yj and count rectangles whose width li >= xj. bisect_left returns the first index where width >= xj, so len(widths) - idx gives the number of rectangles at that height containing the point.

Go Solution

import (
    "sort"
)

func countRectangles(rectangles [][]int, points [][]int) []int {
    // Step 1: Group rectangles by height
    heightToWidths := make([][]int, 101) // Heights 1 to 100
    for _, rect := range rectangles {
        li, hi := rect[0], rect[1]
        heightToWidths[hi] = append(heightToWidths[hi], li)
    }

    // Step 2: Sort widths in each height group
    for h := 1; h <= 100; h++ {
        sort.Ints(heightToWidths[h])
    }

    result := make([]int, len(points))

    // Step 3: For each point, count rectangles containing it
    for i, pt := range points {
        xj, yj := pt[0], pt[1]
        count := 0
        for h := yj; h <= 100; h++ {
            widths := heightToWidths[h]
            idx := sort.Search(len(widths), func(j int) bool {
                return widths[j] >= xj
            })
            count += len(widths) - idx
        }
        result[i] = count
    }
    
    return result
}

Explanation: Go requires explicit slice handling and the use of sort.Search for binary search. Otherwise, the logic mirrors Python. Nil slices behave like empty slices, so we do not need extra checks. Sorting allows binary search, and iteration over heights guarantees counting all relevant rectangles.

Worked Examples

Example 1

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

Group by height:

Height	Widths
2	[1]
3	[2]
5	[2]

Sort widths (already sorted here).
Point (2,1):

Heights 1-100 relevant: heights 1-100 >= y=1 → heights 2,3,5
Count rectangles:
Height 2: widths [1] → widths >=2: 0
Height 3: widths [2] → widths >=2: 1
Height 5: widths [2] → widths >=2: 1
Total: 0+1+1=2

Point (1,4):

Heights >=4 → only height 5
Widths [2] → widths >=1: 1
Total: 1

Output: [2,1]

Example 2

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

Group by height:

Height	Widths
1	[1]
2	[2]
3	[3]

Point (1,3):

Heights >=3 → height 3, widths [3], widths >=1 → 1
Total: 1

Point (1,1):

Heights >=1 → heights 1,2,3
Height 1: widths [1] → widths >=1: 1
Height 2: widths [2] → widths >=1: 1
Height 3: widths [3] → widths >=1: 1
Total: 3

Output: [1,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N + M * H * log N)	O(N) to group rectangles, O(N log N) for sorting (effectively bounded by H=100), O(M * H