Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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
rectangles
are unique.points
are unique.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;
}
};
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;
}
}
# 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
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
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 >>