Problem Description

The "Random Point in Non-overlapping Rectangles" problem asks you to design a data structure that, given a list of rects (where each rectangle is described by its bottom-left and top-right integer coordinates), can efficiently pick a random integer point (x, y) such that:

• Each point within the union of all rectangles is selected with equal probability.
• No rectangles overlap, and all coordinates are integers.

• __init__(self, rects): Initialize the data structure with the given rectangles.
• pick(): Randomly select and return a valid integer point [x, y] from the rectangles, ensuring each point has an equal chance of being picked.

• Each rectangle is represented as [x1, y1, x2, y2], where (x1, y1) is the bottom-left and (x2, y2) is the top-right corner.
• All rectangles are non-overlapping.
• You must not precompute and store all possible points (as this is too slow and memory intensive for large rectangles).

Thought Process

At first glance, the problem seems to invite a brute-force approach: generate all possible integer points in all rectangles, store them, and pick one at random. However, with large rectangles, the number of points grows quickly and storing them all is not feasible.

The key insight is that we do not need to explicitly list all points. Instead, we can:

• Count how many integer points are in each rectangle.
• Pick a random integer in the total range of all points.
• Map that random index back to a specific rectangle and then to a specific point within that rectangle.

Solution Approach

The solution is built on the idea of mapping a random integer (from the total number of possible points) to a specific rectangle and then to a specific point inside that rectangle. Here's how it works step-by-step:

1. Preprocessing:
   • For each rectangle, calculate the number of integer points it contains. For rectangle [x1, y1, x2, y2], the count is (x2 - x1 + 1) * (y2 - y1 + 1).
   • Build a prefix sum array of these counts. This allows us to quickly determine which rectangle a random index falls into.
2. Picking a Point:
   • Generate a random integer k between 0 and total_points - 1.
   • Use binary search on the prefix sum array to find which rectangle contains the k-th point.
   • Compute the offset of k within that rectangle, and then calculate the exact (x, y) coordinates using division and modulo arithmetic.

Example Walkthrough

Suppose: rects = [[1,1,2,2],[3,3,4,4]]

• Rectangle 1: covers points (1,1), (1,2), (2,1), (2,2) → 4 points
• Rectangle 2: covers points (3,3), (3,4), (4,3), (4,4) → 4 points

1. Randomly pick k = 5 (0-based).
2. Prefix sums: [4, 8]. Since 5 < 8 and 5 ≥ 4, rectangle 2 is chosen.
3. Offset within rectangle 2: k - 4 = 1.
4. Rectangle 2's width: 2 (x: 3,4), height: 2 (y: 3,4).
5. Find coordinates:
   • x = 3 + (1 % 2) = 4
   • y = 3 + (1 // 2) = 3
   So the selected point is (4, 3).

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(1) for pick (if all points are precomputed), but O(N * area) to precompute and store all points, where N is number of rectangles.
• Space Complexity: O(total number of points), which can be huge for large rectangles.

• Time Complexity:
  • Initialization: O(N) to compute prefix sums.
  • Pick: O(log N) for binary search + O(1) for coordinate calculation.
• Space Complexity: O(N) for prefix sum and rectangle storage.

Summary

The main insight is to avoid storing all possible points by mapping a random index to a rectangle using prefix sums and binary search. This allows us to efficiently and uniformly pick a random integer point from the union of non-overlapping rectangles, regardless of their size or number. The approach is both time- and space-efficient, leveraging simple arithmetic and search techniques to guarantee uniform randomness.

Code Implementation

import random
import bisect

class Solution:

    def __init__(self, rects):
        self.rects = rects
        self.areas = []
        area_sum = 0
        for x1, y1, x2, y2 in rects:
            area = (x2 - x1 + 1) * (y2 - y1 + 1)
            area_sum += area
            self.areas.append(area_sum)

    def pick(self):
        k = random.randint(1, self.areas[-1])
        rect_index = bisect.bisect_left(self.areas, k)
        x1, y1, x2, y2 = self.rects[rect_index]
        width = x2 - x1 + 1
        prev_area = self.areas[rect_index - 1] if rect_index > 0 else 0
        offset = k - prev_area - 1
        dx = offset % width
        dy = offset // width
        return [x1 + dx, y1 + dy]
      

class Solution {
    vector<vector<int>> rects;
    vector<int> areas;
public:
    Solution(vector<vector<int>>& rects) : rects(rects) {
        int area_sum = 0;
        for (auto& r : rects) {
            int area = (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
            area_sum += area;
            areas.push_back(area_sum);
        }
    }
    
    vector<int> pick() {
        int k = rand() % areas.back() + 1;
        int l = 0, r = areas.size() - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (areas[m] < k) l = m + 1;
            else r = m;
        }
        auto& rect = rects[l];
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        int width = x2 - x1 + 1;
        int prev = l ? areas[l-1] : 0;
        int offset = k - prev - 1;
        int dx = offset % width;
        int dy = offset / width;
        return {x1 + dx, y1 + dy};
    }
};
      

import java.util.*;

class Solution {
    int[][] rects;
    int[] areas;
    Random rand = new Random();
    
    public Solution(int[][] rects) {
        this.rects = rects;
        areas = new int[rects.length];
        int areaSum = 0;
        for (int i = 0; i < rects.length; i++) {
            int[] r = rects[i];
            int area = (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
            areaSum += area;
            areas[i] = areaSum;
        }
    }
    
    public int[] pick() {
        int k = rand.nextInt(areas[areas.length - 1]) + 1;
        int l = 0, r = areas.length - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (areas[m] < k) l = m + 1;
            else r = m;
        }
        int[] rect = rects[l];
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        int width = x2 - x1 + 1;
        int prev = l > 0 ? areas[l-1] : 0;
        int offset = k - prev - 1;
        int dx = offset % width;
        int dy = offset / width;
        return new int[]{x1 + dx, y1 + dy};
    }
}
      

var Solution = function(rects) {
    this.rects = rects;
    this.areas = [];
    let areaSum = 0;
    for (let r of rects) {
        let area = (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
        areaSum += area;
        this.areas.push(areaSum);
    }
};

Solution.prototype.pick = function() {
    let k = Math.floor(Math.random() * this.areas[this.areas.length - 1]) + 1;
    let l = 0, r = this.areas.length - 1;
    while (l < r) {
        let m = Math.floor((l + r) / 2);
        if (this.areas[m] < k) l = m + 1;
        else r = m;
    }
    let rect = this.rects[l];
    let x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
    let width = x2 - x1 + 1;
    let prev = l > 0 ? this.areas[l - 1] : 0;
    let offset = k - prev - 1;
    let dx = offset % width;
    let dy = Math.floor(offset / width);
    return [x1 + dx, y1 + dy];
};