Skip to main content
Talentd

Count Number of Rectangles Containing Each Point - Solution & Explanation

MediumArrayBinary SearchBinary Indexed TreeSorting15 min readAsked at: Amazon, Meta
Practice this problem

Problem Statement

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 * 104
  • rectangles[i].length == points[j].length == 2
  • 1 <= li, xj <= 109
  • 1 <= hi, yj <= 100
  • All the rectangles are unique.
  • All the points are 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.

This C solution initializes an integer array 'count' to keep track of the rectangles containing each point. It iterates through each point and for each point, goes through all the rectangles to check containment. The result is returned as an array of counts.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), where m is the number of points and n is the number of rectangles. Space Complexity: O(m) for the array to store counts.

Try this approach in the editor →

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.

This C solution sorts rectangles by length. For each point, binary search finds the starting index of possible candidate rectangles; a subsequent linear scan ensures only the matching rectangles are counted.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n + m log n). Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(m * n), where m is the number of points and n is the number of rectangles. Space Complexity: O(m) for the array to store counts.

Optimized with Sorting and Binary Search

Time Complexity: O(n log n + m log n). Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Rectangle CheckO(R × P)O(1)Small input sizes or for validating correctness before optimizing
Sorting + Binary Search with Height BucketsO((R + P) log R)O(R)Large inputs with many queries; efficient when rectangle heights are bounded

Video Solution

2250. Count Number of Rectangles Containing Each Point || Leetcode Weekly Contest 290 || • Bro Coders • 2,901 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Count Number of Rectangles Containing Each Point with our built-in code editor and test cases.

Practice on FleetCode
Previous

Queries on Number of Points Inside a Circle