Random Point in Non-overlapping Rectangles

medium math binary search prefix sum randomized

Problem

Build a structure over disjoint rectangles; pick() must return a uniformly random integer point covered by some rectangle.

Inputrects = [[-2,-2,1,1],[2,2,4,6]]

Outputsome point in one of the rectangles

Cumulative area defines pick weights; rand & binary search → rectangle → uniform inside.

rectangles (x1,y1,x2,y2 ; …)

import random, bisect
class Solution:
    def __init__(self, rects):
        self.rects = rects
        self.pref = []
        s = 0
        for x1, y1, x2, y2 in rects:
            s += (x2 - x1 + 1) * (y2 - y1 + 1)
            self.pref.append(s)
    def pick(self):
        target = random.randint(1, self.pref[-1])
        idx = bisect.bisect_left(self.pref, target)
        x1, y1, x2, y2 = self.rects[idx]
        return [random.randint(x1, x2), random.randint(y1, y2)]

class Solution {
  constructor(rects) {
    this.rects = rects;
    this.pref = [];
    let s = 0;
    for (const [x1, y1, x2, y2] of rects) { s += (x2 - x1 + 1) * (y2 - y1 + 1); this.pref.push(s); }
  }
  pick() {
    const t = 1 + Math.floor(Math.random() * this.pref[this.pref.length - 1]);
    let lo = 0, hi = this.pref.length - 1;
    while (lo < hi) { const m = (lo + hi) >> 1; if (this.pref[m] < t) lo = m + 1; else hi = m; }
    const [x1, y1, x2, y2] = this.rects[lo];
    return [x1 + Math.floor(Math.random() * (x2 - x1 + 1)), y1 + Math.floor(Math.random() * (y2 - y1 + 1))];
  }
}

class Solution {
    int[][] rects;
    int[] pref;
    Random rnd = new Random();
    public Solution(int[][] rects) {
        this.rects = rects;
        pref = new int[rects.length];
        int s = 0;
        for (int i = 0; i < rects.length; i++) {
            int[] r = rects[i];
            s += (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
            pref[i] = s;
        }
    }
    public int[] pick() {
        int t = 1 + rnd.nextInt(pref[pref.length - 1]);
        int lo = 0, hi = pref.length - 1;
        while (lo < hi) { int m = (lo + hi) >>> 1; if (pref[m] < t) lo = m + 1; else hi = m; }
        int[] r = rects[lo];
        return new int[]{ r[0] + rnd.nextInt(r[2] - r[0] + 1), r[1] + rnd.nextInt(r[3] - r[1] + 1) };
    }
}

class Solution {
    vector> rects;
    vector pref;
public:
    Solution(vector>& r) : rects(r) {
        int s = 0;
        for (auto& q : r) { s += (q[2] - q[0] + 1) * (q[3] - q[1] + 1); pref.push_back(s); }
    }
    vector pick() {
        int t = 1 + rand() % pref.back();
        int idx = lower_bound(pref.begin(), pref.end(), t) - pref.begin();
        auto& r = rects[idx];
        return { r[0] + rand() % (r[2] - r[0] + 1), r[1] + rand() % (r[3] - r[1] + 1) };
    }
};

Explanation

For the points to be uniform across all rectangles, a bigger rectangle must be chosen more often than a small one — in exact proportion to its number of integer cells (its area). So we pick a rectangle weighted by area, then pick a point uniformly inside it.

In the constructor we compute each rectangle's cell count (x2 - x1 + 1) * (y2 - y1 + 1) and store a prefix sum array pref, where pref[i] is the total cells of rectangles 0 through i. The last entry is the grand total.

To pick, we draw a random target in [1, total] and binary search pref for the first entry that is at least target. That index is the chosen rectangle, and because the prefix ranges are sized by area, each rectangle is hit with the right probability. Then we choose a uniform x in [x1, x2] and y in [y1, y2] inside it.

Example: rectangles with 16 and 25 cells give pref = [16, 41]. A target of 1–16 lands in rectangle 0; a target of 17–41 lands in rectangle 1 — so the second, larger rectangle is correctly picked more often.

Setup is linear in the number of rectangles, and each pick() is one binary search, O(log n).

Time: pick: O(log n) Space: O(n)