Count Number of Rectangles Containing Each Point

// Accepted solution for LeetCode #2250: Count Number of Rectangles Containing Each Point
class Solution {
    public int[] countRectangles(int[][] rectangles, int[][] points) {
        int n = 101;
        List<Integer>[] d = new List[n];
        Arrays.setAll(d, k -> new ArrayList<>());
        for (int[] r : rectangles) {
            d[r[1]].add(r[0]);
        }
        for (List<Integer> v : d) {
            Collections.sort(v);
        }
        int m = points.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int x = points[i][0], y = points[i][1];
            int cnt = 0;
            for (int h = y; h < n; ++h) {
                List<Integer> xs = d[h];
                int left = 0, right = xs.size();
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (xs.get(mid) >= x) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                cnt += xs.size() - left;
            }
            ans[i] = cnt;
        }
        return ans;
    }
}

// Accepted solution for LeetCode #2250: Count Number of Rectangles Containing Each Point
func countRectangles(rectangles [][]int, points [][]int) []int {
	n := 101
	d := make([][]int, 101)
	for _, r := range rectangles {
		d[r[1]] = append(d[r[1]], r[0])
	}
	for _, v := range d {
		sort.Ints(v)
	}
	var ans []int
	for _, p := range points {
		x, y := p[0], p[1]
		cnt := 0
		for h := y; h < n; h++ {
			xs := d[h]
			left, right := 0, len(xs)
			for left < right {
				mid := (left + right) >> 1
				if xs[mid] >= x {
					right = mid
				} else {
					left = mid + 1
				}
			}
			cnt += len(xs) - left
		}
		ans = append(ans, cnt)
	}
	return ans
}

# Accepted solution for LeetCode #2250: Count Number of Rectangles Containing Each Point
class Solution:
    def countRectangles(
        self, rectangles: List[List[int]], points: List[List[int]]
    ) -> List[int]:
        d = defaultdict(list)
        for x, y in rectangles:
            d[y].append(x)
        for y in d.keys():
            d[y].sort()
        ans = []
        for x, y in points:
            cnt = 0
            for h in range(y, 101):
                xs = d[h]
                cnt += len(xs) - bisect_left(xs, x)
            ans.append(cnt)
        return ans

// Accepted solution for LeetCode #2250: Count Number of Rectangles Containing Each Point
/**
 * [2250] Count Number of Rectangles Containing Each Point
 *
 * You are given a 2D integer array rectangles where rectangles[i] = [li, hi] indicates that i^th 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 i^th 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 j^th point.
 * The i^th rectangle contains the j^th 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example1.png" style="width: 300px; height: 509px;" />
 * 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example2.png" style="width: 300px; height: 312px;" />
 * 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 * 10^4
 * 	rectangles[i].length == points[j].length == 2
 * 	1 <= li, xj <= 10^9
 * 	1 <= hi, yj <= 100
 * 	All the rectangles are unique.
 * 	All the points are unique.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/count-number-of-rectangles-containing-each-point/
// discuss: https://leetcode.com/problems/count-number-of-rectangles-containing-each-point/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    // Credit: https://leetcode.com/problems/count-number-of-rectangles-containing-each-point/solutions/1980089/rust-solution-by-akaisiro-3ujx/
    pub fn count_rectangles(rectangles: Vec<Vec<i32>>, points: Vec<Vec<i32>>) -> Vec<i32> {
        let mut group: Vec<Vec<i32>> = vec![Vec::new(); 101];

        rectangles
            .iter()
            .for_each(|x| group[x[1] as usize].push(x[0]));

        group.iter_mut().for_each(|x| x.sort_unstable());

        points
            .iter()
            .map(|i| {
                group
                    .iter()
                    .skip(i[1] as usize)
                    .map(|l| match l.binary_search(&i[0]) {
                        Ok(index) => (l.len() - index) as i32,
                        Err(index) => (l.len() - index) as i32,
                    })
                    .sum::<i32>()
            })
            .collect()
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_2250_example_1() {
        let rectangles = vec![vec![1, 2], vec![2, 3], vec![2, 5]];
        let points = vec![vec![2, 1], vec![1, 4]];

        let result = vec![2, 1];

        assert_eq!(Solution::count_rectangles(rectangles, points), result);
    }

    #[test]
    fn test_2250_example_2() {
        let rectangles = vec![vec![1, 1], vec![2, 2], vec![3, 3]];
        let points = vec![vec![1, 3], vec![1, 1]];

        let result = vec![1, 3];

        assert_eq!(Solution::count_rectangles(rectangles, points), result);
    }
}

// Accepted solution for LeetCode #2250: Count Number of Rectangles Containing Each Point
function countRectangles(rectangles: number[][], points: number[][]): number[] {
    const n = 101;
    let ymap = Array.from({ length: n }, v => []);
    for (let [x, y] of rectangles) {
        ymap[y].push(x);
    }
    for (let nums of ymap) {
        nums.sort((a, b) => a - b);
    }
    let ans = [];
    for (let [x, y] of points) {
        let count = 0;
        for (let h = y; h < n; h++) {
            const nums = ymap[h];
            let left = 0,
                right = nums.length;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (x > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            count += nums.length - right;
        }
        ans.push(count);
    }
    return ans;
}