304 North Cardinal St.
Dorchester Center, MA 02124

# Count Number of Rectangles Containing Each Point LeetCode Solution

## Problem – Count Number of Rectangles Containing Each Point LeetCode Solution

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.

### Count Number of Rectangles Containing Each Point LeetCode Solution in C++

``````class Solution {
public:

// helper fxn for binary search
int binsear(vector<int>& arr, int x){
int l=0, r=arr.size()-1;

int anstillnow=arr.size();
// if we find no m such that arr[m]>=x, means that our x is greater than all values of length, in such case we return idx n (i.e. size of arr)
// reason being, we substract our idx by size of arr to get number of rectangles greater than that in main fxn, so return arr.size would give us 0 (which we want)

while(l<=r){
int m= l + (r-l)/2;

if(arr[m]>=x){
anstillnow=m;
r=m-1;
}
else{
l=m+1;
}

}

return anstillnow;
}

vector<int> countRectangles(vector<vector<int>>& rect, vector<vector<int>>& points) {

unordered_map<int, vector<int>> htl;
// maps heights to all the lengths of rectangles with that height

for(int i=0; i<rect.size(); i++){
htl[rect[i]].push_back(rect[i]);
}

// have to sort the containers to apply binary search
for(int i=0; i<=100; i++){
sort(htl[i].begin(), htl[i].end());
}

vector<int> ans;

for(vector<int> p: points){
int x=p, y=p;
int ct=0;
for(int j= y; j<=100; j++){
if(htl.find(j)!=htl.end()){
ct+= htl[j].size()- binsear(htl[j], x);
// binary search return the idx in array from which the values are >= x
// the values at this and right of this are the lengths possible
// so substract by size of array to get the number
}
}

ans.push_back(ct);

}

return ans;
}
};
``````

### Count Number of Rectangles Containing Each Point LeetCode Solution in Java

``````class Solution {

// helper fxn for binary search
int binsear(ArrayList<Integer> arr, int x){
int l=0, r=arr.size()-1;

int anstillnow=arr.size();
// if we find no m such that arr[m]>=x, means that our x is greater than all values of length, in such case we return idx n (i.e. size of arr)
// reason being, we substract our idx by size of arr to get number of rectangles greater than that in main fxn, so return arr.size would give us 0 (which we want)

while(l<=r){
int m= l + (r-l)/2;

if(arr.get(m)>=x){
anstillnow=m;
r=m-1;
}
else{
l=m+1;
}

}

return anstillnow;
}

public int[] countRectangles(int[][] rect, int[][] points) {
HashMap<Integer, ArrayList<Integer>> htl= new HashMap<>();
// maps heights to all the lengths of rectangles with that height

for(int i=0; i<rect.length; i++){
else
{
htl.put(rect[i],new ArrayList<>());
}
}

// have to sort the container to apply binary search
for(int a:htl.keySet()){
Collections.sort(htl.get(a));
}

int[] ans = new int[points.length];

for(int i=0;i<points.length;i++){
int x=points[i], y=points[i];
int ct=0;
for(int j= y; j<=100; j++){
if(htl.containsKey(j)){
ct+= htl.get(j).size()- binsear(htl.get(j), x);
// binary search return the idx in array from which the values are >= x
// the values at this and right of this are the lengths possible
// so substract by size of array to get the number
}
}

ans[i]=ct;

}

return ans;
}
}
``````

### Count Number of Rectangles Containing Each Point LeetCode Solution in Python

``````# helper fxn for binary search
def binsear(arr, x):
l=0
r=len(arr)-1

anstillnow=len(arr)
# if we find no m such that arr[m]>=x, means that our x is greater than all values of length, in such case we return idx n (i.e. size of arr)
# reason being, we substract our idx by size of arr to get number of rectangles greater than that in main fxn, so return arr.size would give us 0 (which we want)

while(l<=r):
m= l + (r-l)//2

if(arr[m]>=x):
anstillnow=m
r=m-1;

else:
l=m+1

return anstillnow

class Solution:

def countRectangles(self, rect: List[List[int]], points: List[List[int]]) -> List[int]:

# create a dictionary of int -> list of int
htl=defaultdict(list)

# maps heights to all the lengths of rectangles with that height
for l, h in rect:
htl[h].append(l)

# have to sort the containers to apply binary search
for k,v in htl.items():
v.sort()

ans=[];

for p in points:
x=p
y=p

ct=0

for j in range(y, 101):
if j in htl:
ct+= len(htl[j]) - binsear(htl[j], x)

# binary search return the idx in array from which the values are >= x
# the values at this and right of this are the lengths possible
# so substract by size of array to get the number

ans.append(ct)

return ans
``````
##### Count Number of Rectangles Containing Each Point LeetCode Solution Review:

In our experience, we suggest you solve this Count Number of Rectangles Containing Each Point LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Count Number of Rectangles Containing Each Point LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Count Number of Rectangles Containing Each Point LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions