Random Point in Non-overlapping Rectangles

Med

#0484Time: - **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.

Patterns

Math Prefix Sum Randomized

Algorithms

Binary Search Reservoir Sampling

Data structures

Array Ordered Set

Prompt

You are given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [a_i, b_i, x_i, y_i] indicates that (a_i, b_i) is the bottom-left corner point of the i^th rectangle and (x_i, y_i) is the top-right corner point of the i^th 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:

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
-10⁹ <= a_i < x_i <= 10⁹
-10⁹ <= b_i < y_i <= 10⁹
x_i - a_i <= 2000
y_i - b_i <= 2000
All the rectangles do not overlap.
At most 10⁴ calls will be made to pick.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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].

Walkthrough

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.

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.
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.
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.

1import java.util.ArrayList;2import java.util.List;3import java.util.Random;4 5class Solution {6    private int[][] rects;7    private List<Integer> pointCounts;8    private int totalPoints;9    private Random random;10 11    public Solution(int[][] rects) {12        this.rects = rects;13        this.pointCounts = new ArrayList<>();14        this.totalPoints = 0;15        this.random = new Random();16 17        for (int[] rect : rects) {18            int pointsInRect = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);19            this.totalPoints += pointsInRect;20            this.pointCounts.add(pointsInRect);21        }22    }23 24    public int[] pick() {25        int target = random.nextInt(totalPoints) + 1; // 1-based index26        int rectIndex = 0;27 28        for (int i = 0; i < pointCounts.size(); i++) {29            if (target <= pointCounts.get(i)) {30                rectIndex = i;31                break;32            }33            target -= pointCounts.get(i);34        }35 36        int[] rect = rects[rectIndex];37        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];38        39        int randX = x1 + random.nextInt(x2 - x1 + 1);40        int randY = y1 + random.nextInt(y2 - y1 + 1);41 42        return new int[]{randX, randY};43    }44}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int[] s;4private5  int[][] rects;6private7  Random random = new Random();8public9  Solution(int[][] rects) {10    int n = rects.length;11    s = new int[n + 1];12    for (int i = 0; i < n; ++i) {13      s[i + 1] = s[i] + (rects[i][2] - rects[i][0] + 1) *14                            (rects[i][3] - rects[i][1] + 1);15    }16    this.rects = rects;17  }18public19  int[] pick() {20    int n = rects.length;21    int v = 1 + random.nextInt(s[n]);22    int left = 0, right = n;23    while (left < right) {24      int mid = (left + right) >> 1;25      if (s[mid] >= v) {26        right = mid;27      } else {28        left = mid + 1;29      }30    }31    int[] rect = rects[left - 1];32    return new int[]{rect[0] + random.nextInt(rect[2] - rect[0] + 1),33                     rect[1] + random.nextInt(rect[3] - rect[1] + 1)};34  }35} /** * Your Solution object will be instantiated and called as such: * Solution36     obj = new Solution(rects); * int[] param_1 = obj.pick(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem