Physical Address
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 * 104rectangles[i].length == points[j].length == 21 <= li, xj <= 1091 <= hi, yj <= 100- All the
rectanglesare unique. - All the
pointsare 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][1]].push_back(rect[i][0]);
}
// 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[0], y=p[1];
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++){
if(htl.containsKey(rect[i][1])) htl.get(rect[i][1]).add(rect[i][0]);
else
{
htl.put(rect[i][1],new ArrayList<>());
htl.get(rect[i][1]).add(rect[i][0]);
}
}
// 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][0], y=points[i][1];
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[0]
y=p[1]
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
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 >>
