# Random Point in Non-overlapping Rectangles
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/random-point-in-non-overlapping-rectangles)
Canonical: https://scaleengineer.com/dsa/problems/random-point-in-non-overlapping-rectangles
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Reservoir Sampling](https://scaleengineer.com/algorithms/reservoir-sampling)
**Data structures:** Array, Ordered Set
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/random-point-in-non-overlapping-rectangles/image0.jpg) 

**Input**
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
**Output**
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

**Explanation**
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]

**Constraints:**

* `1 <= rects.length <= 100`
* `rects[i].length == 4`
* `-109 <= ai < xi <= 109`
* `-109 <= bi < yi <= 109`
* `xi - ai <= 2000`
* `yi - bi <= 2000`
* All the rectangles do not overlap.
* At most `104` calls will be made to `pick`.

# Approaches
## Weighted Random Selection with Linear Scan
This approach involves two main steps. First, we pre-calculate the number of integer points each rectangle contains and the total number of points. To pick a point, we first select a rectangle with a probability proportional to its number of points, and then we pick a uniform random point within that chosen rectangle. The rectangle selection is done by linearly scanning through the rectangles' point counts.
**Time:** - **Constructor:** `O(N)`, where N is the number of rectangles, as we iterate through them once to calculate point counts.
- **`pick()`:** `O(N)` in the worst case, as we might need to iterate through all N rectangles to select one. · **Space:** O(N) to store the point counts for each of the N rectangles.
**Pros:** Relatively simple to understand and implement.; Correctly provides a uniform distribution over all possible integer points.; Constructor is efficient with O(N) time complexity.
**Cons:** The `pick()` operation has a time complexity of O(N), where N is the number of rectangles. This can be slow if `pick()` is called many times with a large N.
### Explanation
### Constructor (`Solution(int[][] rects)`)
In the constructor, we process the input rectangles to prepare for the `pick` operation. We iterate through each rectangle `[a, b, x, y]` and calculate the number of integer points it contains using the formula `(x - a + 1) * (y - b + 1)`. These counts are stored in a list, and we also compute the sum of all these counts, which gives us the `totalPoints` across all rectangles.

### Pick Method (`int[] pick()`)
To ensure every point has an equal chance of being selected, we use a weighted random selection strategy. 
1. We pick a random integer `target` from 1 to `totalPoints`. This `target` conceptually represents the k-th point if all points from all rectangles were laid out in a single sequence.
2. We then iterate through our list of point counts. For each rectangle, we check if our `target` falls within the range of points contributed by that rectangle. We do this by seeing if `target` is less than or equal to the current rectangle's point count. If it is, we've found our rectangle. If not, we subtract the current rectangle's point count from `target` and move to the next one.
3. After identifying the correct rectangle, we generate a random integer point within its boundaries. A random x-coordinate is chosen from its horizontal range, and a random y-coordinate from its vertical range. This final point `[u, v]` is then returned.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private int[][] rects;
    private List<Integer> pointCounts;
    private int totalPoints;
    private Random random;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.pointCounts = new ArrayList<>();
        this.totalPoints = 0;
        this.random = new Random();

        for (int[] rect : rects) {
            int pointsInRect = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            this.totalPoints += pointsInRect;
            this.pointCounts.add(pointsInRect);
        }
    }

    public int[] pick() {
        int target = random.nextInt(totalPoints) + 1; // 1-based index
        int rectIndex = 0;

        for (int i = 0; i < pointCounts.size(); i++) {
            if (target <= pointCounts.get(i)) {
                rectIndex = i;
                break;
            }
            target -= pointCounts.get(i);
        }

        int[] rect = rects[rectIndex];
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        
        int randX = x1 + random.nextInt(x2 - x1 + 1);
        int randY = y1 + random.nextInt(y2 - y1 + 1);

        return new int[]{randX, randY};
    }
}
```
### Algorithm
- **Constructor (`Solution(int[][] rects)`):**
  - Initialize an array or list, `pointCounts`, to store the number of integer points for each rectangle.
  - Initialize a variable `totalPoints` to 0.
  - For each rectangle `rect` in `rects`:
    - Calculate the number of points: `count = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)`.
    - Add `count` to `pointCounts`.
    - Add `count` to `totalPoints`.
- **Pick Method (`int[] pick()`):**
  - Generate a random integer `target` between 1 and `totalPoints`.
  - Iterate through the `pointCounts` from index `i = 0` to `N-1`:
    - If `target` is less than or equal to `pointCounts[i]`, this means the point falls into the current rectangle `i`. Select this rectangle and break the loop.
    - Otherwise, subtract `pointCounts[i]` from `target` and continue to the next rectangle.
  - Once a rectangle `[a, b, x, y]` is chosen:
    - Generate a random x-coordinate `u` in the range `[a, x]`.
    - Generate a random y-coordinate `v` in the range `[b, y]`.
  - Return the point `[u, v]`.

## Weighted Random Selection using Prefix Sums and Binary Search
This is an optimized version of the weighted random selection approach. Instead of linearly scanning to find the right rectangle, we use a more efficient data structure. By pre-calculating the prefix sums of the point counts, we can use binary search to select a rectangle in logarithmic time. This significantly improves the performance of the `pick` operation, especially when it's called many times.
**Time:** - **Constructor:** `O(N)`, where N is the number of rectangles, to build the prefix sum array.
- **`pick()`:** `O(log N)` due to the binary search on the prefix sum array. · **Space:** O(N) to store the prefix sum array for the N rectangles.
**Pros:** Highly efficient `pick()` operation with O(log N) time complexity.; Maintains the correctness of uniform random point selection.; Optimal for scenarios where `pick()` is called frequently.
**Cons:** Slightly more complex to implement due to the binary search logic.
### Explanation
### Constructor (`Solution(int[][] rects)`)
The key idea is to map the 2D problem into a 1D problem. We can imagine all the integer points from all rectangles concatenated into a single, long array. The constructor's job is to figure out the size of this conceptual array and the boundaries for each rectangle's segment within it. We create a `prefixSums` array where `prefixSums[i]` stores the total number of points in rectangles `0` through `i`. This is done by iterating through the rectangles, calculating the points in each, and keeping a running total which is stored at each step.

### Pick Method (`int[] pick()`)
With the `prefixSums` array, picking a point becomes a two-step process:
1.  **Select a Rectangle:** We generate a random integer `target` from `0` to `totalPoints - 1`. This `target` is an index into our conceptual 1D array of all points. We then use binary search on the `prefixSums` array to efficiently find which rectangle this index falls into. The binary search looks for the first cumulative sum that is greater than our `target` value. The index of this sum corresponds to the index of our chosen rectangle.
2.  **Select a Point in the Rectangle:** Once the rectangle is chosen, we generate a random point within its boundaries, just as in the previous approach. A random x-coordinate is chosen from `[x1, x2]` and a random y-coordinate from `[y1, y2]`.

This method reduces the time complexity of picking a rectangle from O(N) to O(log N).

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private int[][] rects;
    private List<Integer> prefixSums;
    private int totalPoints;
    private Random random;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.prefixSums = new ArrayList<>();
        this.random = new Random();
        int currentSum = 0;

        for (int[] rect : rects) {
            int pointsInRect = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            currentSum += pointsInRect;
            prefixSums.add(currentSum);
        }
        this.totalPoints = currentSum;
    }

    public int[] pick() {
        int target = random.nextInt(totalPoints);
        
        // Binary search to find the rectangle index
        int low = 0, high = prefixSums.size() - 1;
        int rectIndex = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target < prefixSums.get(mid)) {
                rectIndex = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        int[] rect = rects[rectIndex];
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        
        int randX = x1 + random.nextInt(x2 - x1 + 1);
        int randY = y1 + random.nextInt(y2 - y1 + 1);

        return new int[]{randX, randY};
    }
}
```
### Algorithm
- **Constructor (`Solution(int[][] rects)`):**
  - Initialize a list, `prefixSums`, to store the cumulative sum of points.
  - Initialize a running sum `currentSum = 0`.
  - For each rectangle `rect` in `rects`:
    - Calculate `count = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)`.
    - Add `count` to `currentSum`.
    - Add the new `currentSum` to the `prefixSums` list.
  - The last element of `prefixSums` is the total number of points.
- **Pick Method (`int[] pick()`):**
  - Get the total number of points, `totalPoints`, from the last element of `prefixSums`.
  - Generate a random integer `target` between 0 and `totalPoints - 1`.
  - Use binary search on `prefixSums` to find the first index `i` where `target < prefixSums[i]`. This index `i` is the index of the chosen rectangle.
  - Once a rectangle `[a, b, x, y]` is chosen:
    - Generate a random x-coordinate `u` in the range `[a, x]`.
    - Generate a random y-coordinate `v` in the range `[b, y]`.
  - Return the point `[u, v]`.

# Solutions
### Java

```java
class Solution {
private
  int[] s;
private
  int[][] rects;
private
  Random random = new Random();
public
  Solution(int[][] rects) {
    int n = rects.length;
    s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + (rects[i][2] - rects[i][0] + 1) *
                            (rects[i][3] - rects[i][1] + 1);
    }
    this.rects = rects;
  }
public
  int[] pick() {
    int n = rects.length;
    int v = 1 + random.nextInt(s[n]);
    int left = 0, right = n;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (s[mid] >= v) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    int[] rect = rects[left - 1];
    return new int[]{rect[0] + random.nextInt(rect[2] - rect[0] + 1),
                     rect[1] + random.nextInt(rect[3] - rect[1] + 1)};
  }
} /** * Your Solution object will be instantiated and called as such: * Solution
     obj = new Solution(rects); * int[] param_1 = obj.pick(); */

```

### CPP

```cpp
class Solution { public: vector < int > s ; vector < vector < int >> rects ; Solution ( vector < vector < int >>& rects ) { int n = rects . size (); s . resize ( n + 1 ); for ( int i = 0 ; i < n ; ++ i ) s [ i + 1 ] = s [ i ] + ( rects [ i ][ 2 ] - rects [ i ][ 0 ] + 1 ) * ( rects [ i ][ 3 ] - rects [ i ][ 1 ] + 1 ); this -> rects = rects ; srand ( time ( nullptr )); } vector < int > pick () { int n = rects . size (); int v = 1 + rand () % s [ n ]; int idx = lower_bound ( s . begin (), s . end (), v ) - s . begin (); auto & rect = rects [ idx - 1 ]; int x = rect [ 0 ] + rand () % ( rect [ 2 ] - rect [ 0 ] + 1 ); int y = rect [ 1 ] + rand () % ( rect [ 3 ] - rect [ 1 ] + 1 ); return { x , y }; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(rects); * vector<int> param_1 = obj->pick(); */
```

### Python

```python
class Solution:
    # Your Solution object will be instantiated and called as such: # obj = Solution(rects) # param_1 = obj.pick()
    def __init__(self, rects: List[List[int]]): self . rects = rects self . s = [0] * len(rects) for i, (x1, y1, x2, y2) in enumerate(rects): self . s[i] = self . s[i - 1] + (x2 - x1 + 1) * (y2 - y1 + 1) def pick(self) -> List[int]: v = random . randint(1, self . s[- 1]) idx = bisect_left(self . s, v) x1, y1, x2, y2 = self . rects[idx] return [random . randint(x1, x2), random . randint(y1, y2)]

```