You are given a set of non-overlapping axis-aligned rectangles. Each rectangle is represented as:

[x1, y1, x2, y2]

Where:

• (x1, y1) is the bottom-left coordinate
• (x2, y2) is the top-right coordinate
• All values are integers
• Rectangles do not overlap

Your task:

Design a data structure that supports:

Solution(rects)   // initializes with given rectangles
pick()            // randomly returns an (x, y) integer point

The catch:

Every integer point covered by the rectangles must have an equal probability of being chosen.

Example:

Input:
rects = [[1,1,5,5]]

pick() → might return any point (x,y) where x ∈ [1,5], y ∈ [1,5]

---

Problem Understanding

Important characteristics:

• Rectangles are guaranteed not to overlap
• All coordinates are integers
• A rectangle contains:

(width + 1) * (height + 1) integer points

because both edges are inclusive

Goal:

Ensure uniform random distribution across all points from all rectangles.

Meaning:

• You cannot pick a rectangle uniformly
• You must pick based on area (number of integer points)

---

Logic Explained in Simple English

To solve this fairly, think of the problem in three steps:

Step 1: Compute how many integer points each rectangle contains

For rectangle [x1, y1, x2, y2]:

count = (x2 - x1 + 1) * (y2 - y1 + 1)

Step 2: Build a prefix sum array

This lets us know cumulative point counts across rectangles.

Example:

rect counts: [12, 20, 7]
prefix sum:  [12, 32, 39]

Step 3: When pick() is called:

1. Generate a random integer target between 1 and total points
2. Binary search in prefix sums to find which rectangle the target falls into
3. Pick a random point inside that rectangle:
   • random x in [x1, x2]
   • random y in [y1, y2]

Why this works:

• Prefix sum maps total probability space to rectangles
• Binary search finds the correct weighted rectangle
• Picking uniformly inside rectangle ensures equal probability

This guarantees uniformity across all points.

---

Step-by-Step Approach

1. Store rectangles
2. Compute number of integer points in each rectangle
3. Build prefix sums
4. Total points = last prefix entry
5. On pick():
   • Randomly choose target index in [1, total]
   • Binary search prefix array to find rectangle index
   • Randomly generate coordinates inside selected rectangle
   • Return the point

---

Java Implementation

class Solution {

    private int[][] rects;
    private int[] prefix;
    private int totalPoints;
    private Random rand;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.prefix = new int[rects.length];
        this.rand = new Random();

        int runningSum = 0;
        for (int i = 0; i < rects.length; i++) {
            int[] r = rects[i];
            int count = (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
            runningSum += count;
            prefix[i] = runningSum;
        }

        totalPoints = runningSum;
    }

    public int[] pick() {
        int target = rand.nextInt(totalPoints) + 1;

        int idx = binarySearch(target);

        int[] r = rects[idx];

        int x = r[0] + rand.nextInt(r[2] - r[0] + 1);
        int y = r[1] + rand.nextInt(r[3] - r[1] + 1);

        return new int[]{x, y};
    }

    private int binarySearch(int target) {
        int left = 0;
        int right = prefix.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefix[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

---

Dry Run Example

Rectangles:

rects = [
  [1,1,2,2],   // points = 4
  [5,5,6,6],   // points = 4
  [10,10,13,11] // points = 8
]

Step 1 — Point counts:

4, 4, 8

Step 2 — Prefix sums:

[4, 8, 16]

totalPoints = 16

pick() call example:

Random target = 9

Binary search:

• 9 > 8 → target falls in rectangle index 2

Pick random point inside last rectangle:

x range = [10,13]
y range = [10,11]

Example result:

[12,11]

All 16 integer points across all rectangles are equally likely.

---

Time and Space Complexity

Initialization

Time:  O(n)
Space: O(n)

pick()

Time:  O(log n) for binary search
       + O(1) to generate point

Total Efficiency

Very fast even with many rectangles.

---

Common Mistakes and How to Avoid Them

Mistake 1: Picking rectangles uniformly

This breaks fairness if rectangles have different sizes.

Mistake 2: Forgetting +1 when counting points

Coordinates are inclusive.

Mistake 3: Incorrect binary search target range

Must draw integer in:

[1, totalPoints]

Mistake 4: Using floating-point probability math

Leads to rounding issues — stick to integer counts.

Mistake 5: Returning same seeds

Use a persistent Random instance, not new Random() on each pick.