Count number of rectangles containing each point

Array Hash Table Binary Search Binary Indexed Tree Sorting

37.4% acceptance

Feb 25, 2026

554

141

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_rectangles(rectangles: Vec<Vec<i32>>, points: Vec<Vec<i32>>) -> Vec<i32> {
    // Group rectangle widths by height (height <= 100)
    let mut by_height: Vec<Vec<i32>> = vec![Vec::new(); 101];
    for rect in &rectangles {
      let (l, h) = (rect[0], rect[1] as usize);
      by_height[h].push(l);
    }
    // Sort each group
    for h in 0..=100 {
      by_height[h].sort_unstable();
    }

    points.iter().map(|p| {
      let (x, y) = (p[0], p[1] as usize);
      let mut count = 0;
      for h in y..=100 {
        let widths = &by_height[h];
        if widths.is_empty() { continue; }
        // Count widths >= x using binary search
        let pos = widths.partition_point(|&w| w < x);
        count += (widths.len() - pos) as i32;
      }
      count
    }).collect()
  }
}