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 * 104rectangles[i].length == points[j].length == 21 <= li, xj <= 1091 <= hi, yj <= 100rectangles are unique.points are unique.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n + m log n). Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| 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). |
The Most Confusing FAANG Interview Question! | Count And Say - Leetcode 38 • Greg Hogg • 33,962 views views
Watch 9 more video solutions →Practice Count Number of Rectangles Containing Each Point with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor