Random point in non overlapping rectangles

Array Math Binary Search Reservoir Sampling Prefix Sum Ordered Set Randomized

39.4% acceptance

Jan 13, 2026

520

689

You are given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [ai, bi, xi, yi] indicates that (ai, bi) is the bottom-left corner point of the ith rectangle and (xi, yi) is the top-right corner point of the ith rectangle. Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle. Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned. Note that an integer point is a point that has integer coordinates. Implement the Solution class: Solution(int[][] rects) Initializes the object with the given rectangles rects. int[] pick() Returns a random integer point [u, v] inside the space covered by one of the given rectangles.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use rand::Rng;

struct Solution {
  rects: Vec<Vec<i32>>,
  areas: Vec<i32>,
  total_area: i32,
}


/** 
 *  * `&self` means the method takes an immutable reference.
 *  * If you need a mutable reference, change it to `&mut self` instead.
 *  */
impl Solution {

  fn new(rects: Vec<Vec<i32>>) -> Self {
    let mut areas = Vec::new();
    let mut total_area = 0;
    
    for rect in &rects {
      let area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
      total_area += area;
      areas.push(total_area);
    }
    
    Solution {
      rects,
      areas,
      total_area,
    }
  }

  fn pick(&self) -> Vec<i32> {
    let mut rng = rand::rng();
    let target = rng.random_range(0..self.total_area);
    
    // Binary search to find which rectangle
    let mut left = 0;
    let mut right = self.areas.len() - 1;
    
    while left < right {
      let mid = left + (right - left) / 2;
      if self.areas[mid] <= target {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    let rect = &self.rects[left];
    let x = rng.random_range(rect[0]..=rect[2]);
    let y = rng.random_range(rect[1]..=rect[3]);
    
    vec![x, y]
  }
}