497. Random Point in Non-overlapping Rectangles

MediumReservoir SamplingArrayMathBinary SearchOrdered SetPrefix SumRandomized
Leetcode Link

Problem Description

In this LeetCode problem, we are given a list of axis-aligned rectangles defined by their coordinates. Each rectangle is represented as [a_i, b_i, x_i, y_i] where (a_i, b_i) is the bottom-left corner and (x_i, y_i) is the top-right corner of the ith rectangle. The goal is to create an algorithm that can randomly pick a point within the space covered by these rectangles. A point exactly on the edge of a rectangle is still considered to be within the rectangle. The algorithm must ensure any integer point in the space is equally likely to be chosen.

Intuition

To solve this problem, the solution must be able to pick a random point with uniform probability from the space defined by the rectangles. The main challenge is that the rectangles might have different areas, so simply picking a random rectangle and then a random point within it wouldn't yield a uniform distribution over all possible points.

Here's the intuition behind the solution:

  1. First, we calculate the area of each rectangle, which is the total number of integer points that can exist within that rectangle including the edges. For example, the area can be calculated by multiplying the width (x2 - x1 + 1) with the height (y2 - y1 + 1).

  2. We use a prefix sum array to keep a running total of the areas of all rectangles up to the current index. This way, each entry self.s[i] in the prefix sum array contains the total number of points that can be picked from the first i+1 rectangles.

  3. To pick a random point, we first decide which rectangle the point will be in. We do this by picking a random integer v between 1 and the sum of all rectangle areas (i.e., self.s[-1]). We use a binary search (through bisect_left) to find the first rectangle in the prefix sum array such that the running sum is greater than or equal to v. This effectively selects a rectangle with a probability proportional to its area.

  4. Once the rectangle is selected, we randomly pick a point within it. We use random.randint to select an integer x coordinate between x1 and x2, and a y coordinate between y1 and y2. The combination of [x, y] gives us our random point within the chosen rectangle.

By ensuring that larger rectangles (with more possible points) are more likely to be chosen, and then evenly picking a point within the selected rectangle, the algorithm guarantees that any point in any rectangle is equally likely to be returned.

Learn more about Math, Binary Search and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The implementation of the solution uses a combination of prefix sums, binary search, and random selection to accomplish the goal of picking a random point according to the described probability distribution.

Here's a breakdown of how the solution approach is implemented:

  1. Prefix Sum Array: In the __init__ method, we initialize an array self.s to store the prefix sums of the areas of the given rectangles. This array is critical in helping us determine which rectangle should contain the randomly picked point. The area of a rectangle is calculated by (x2 - x1 + 1) * (y2 - y1 + 1), which includes all integer points inside and on the edge of each rectangle.

  2. Cumulative Area Sum: We iterate over the rects array and accumulate the area of the rectangles. This cumulative sum represents the total number of points we can pick from up to the current rectangle. It gives us a way to select a rectangle proportional to its area size; rectangles with larger areas have a broader range in the prefix sum array and thus have a higher probability of being selected.

  3. Random Point Selection: In the pick method, we first select a rectangle. We generate a random integer v between 1 and self.s[-1], which is the sum of areas of all rectangles. Using the bisect_left function, we find the index idx such that self.s[idx] is the smallest number in the prefix sum that is greater than or equal to v. This index corresponds to the rectangle in which the point will be located.

  4. Random Point within the Rectangle: Once we have the rectangle, we use random.randint twice to get random x and y coordinates within the selected rectangle. The function random.randint(a, b) selects a random integer between a and b (inclusive), which is used to find the x coordinate within [x1, x2] and the y coordinate within [y1, y2].

  5. Return the Point: The random x and y values are combined into a list [x, y] representing the random point's coordinates. This point is guaranteed to be within the rectangle found in the previous steps, and the method returns this point.

The use of prefix sums and binary search allows the algorithm to efficiently handle the selection of rectangles with different area sizes, ensuring that the likelihood of picking any given point remains uniform across the entire space defined by rects.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Imagine we have three rectangles represented as follows:

  • Rectangle 1: [1, 1, 3, 3]
  • Rectangle 2: [4, 4, 5, 5]
  • Rectangle 3: [6, 6, 8, 8]

Their areas are calculated as:

  • Area of Rectangle 1: (3 - 1 + 1) * (3 - 1 + 1) = 9
  • Area of Rectangle 2: (5 - 4 + 1) * (5 - 4 + 1) = 4
  • Area of Rectangle 3: (8 - 6 + 1) * (8 - 6 + 1) = 9

Now, let's create the prefix sum array (assuming we've already sorted our rectangles):

  • Prefix sum after Rectangle 1: 9
  • Prefix sum after Rectangle 2: 9 (previous) + 4 = 13
  • Prefix sum after Rectangle 3: 13 (previous) + 9 = 22

The prefix sums array looks like this: self.s = [9, 13, 22].

When we call the pick method, here's what happens:

  1. We select a random integer v between 1 and 22. Let's say v = 10.
  2. Using binary search (bisect_left), we find the first index in self.s that is not less than 10. In our prefix sums array, this is index 1.
  3. This index corresponds to Rectangle 2 because self.s[0] < v โ‰ค self.s[1].
  4. We then pick a random point within Rectangle 2. The x coordinate is picked between 4 and 5, and the y coordinate is also picked between 4 and 5. Assuming random.randint gives us x = 4 and y = 4, our chosen point is [4, 4].

This example illustrates how each rectangle gets a chance proportional to its area to be selected for picking a point, ensuring a uniform distribution over all integer points within the space of the rectangles provided.

Solution Implementation

1import random
2from bisect import bisect_left
3from typing import List
4
5class Solution:
6    def __init__(self, rects: List[List[int]]):
7        # Initialize the Solution object with a list of rectangles defined by bottom-left and top-right coordinates
8        self.rectangles = rects
9        # An array to store the accumulated count of points in all rectangles
10        self.accumulated_counts = [0] * len(rects)
11        for i, (x1, y1, x2, y2) in enumerate(rects):
12            # Calculate the count of points in the current rectangle and add it to the previous accumulated count
13            # The count for a rectangle is the number of integer points inside it, which is (width * height)
14            self.accumulated_counts[i] = self.accumulated_counts[i - 1] + (x2 - x1 + 1) * (y2 - y1 + 1)
15
16    def pick(self) -> List[int]:
17        # Pick a random integer point from the total number of points in all rectangles
18        point_choice = random.randint(1, self.accumulated_counts[-1])
19        # Find the rectangle that the point_choice falls into using binary search
20        rectangle_index = bisect_left(self.accumulated_counts, point_choice)
21        # Unpack the coordinates of the chosen rectangle
22        x1, y1, x2, y2 = self.rectangles[rectangle_index]
23        # Transform the point_choice to fit within the range of the chosen rectangle
24        # The point_choice is adjusted to start from 0 for the selected rectangle by subtracting the accumulated count of the previous rectangles
25        adjusted_count = point_choice - (self.accumulated_counts[rectangle_index - 1] if rectangle_index > 0 else 0)
26        # Calculate the width and height of the chosen rectangle
27        width, height = x2 - x1 + 1, y2 - y1 + 1
28        # Find the coordinates within the rectangle by using adjusted count, width, and height
29        # The adjusted x coordinate is obtained by taking adjusted_count modulo width
30        # The adjusted y coordinate is obtained by dividing the adjusted_count by width
31        x = x1 + (adjusted_count - 1) % width
32        y = y1 + (adjusted_count - 1) // width
33        # Return the random point coordinates
34        return [x, y]
35
36
37# Your Solution object will be instantiated and called as such:
38# obj = Solution(rects)
39# param_1 = obj.pick()
40
1import java.util.Random;
2
3class Solution {
4    private final int[] prefixSums;
5    private final int[][] rectangles;
6    private final Random random = new Random();
7
8    public Solution(int[][] rects) {
9        int n = rects.length;
10        this.rectangles = rects;
11        prefixSums = new int[n + 1]; // Prefix sums of areas to help with random selection
12      
13        // Pre-compute the prefix sum array where each entry represents the total number
14        // of points from the start up to and including the current rectangle.
15        for (int i = 0; i < n; ++i) {
16            // Calculate the area of the current rectangle using (width * height)
17            // and add it to the prefix sum.
18            prefixSums[i + 1] = prefixSums[i] +
19                (rectangles[i][2] - rectangles[i][0] + 1) *
20                (rectangles[i][3] - rectangles[i][1] + 1);
21        }
22    }
23
24    public int[] pick() {
25        int n = rectangles.length;
26        // Pick a random value that falls within the range of total number of points.
27        int randomValue = 1 + random.nextInt(prefixSums[n]);
28      
29        // Binary search to find the rectangle that the point falls into based
30        // on the randomValue.
31        int left = 0, right = n;
32        while (left < right) {
33            int mid = left + (right - left) / 2;
34            if (prefixSums[mid] >= randomValue) {
35                right = mid;
36            } else {
37                left = mid + 1;
38            }
39        }
40      
41        // Get the rectangle where the point falls into.
42        int[] selectedRect = rectangles[left - 1];
43      
44        // Randomly pick a point within the selected rectangle.
45        return new int[] {
46            // X coordinate
47            selectedRect[0] + random.nextInt(selectedRect[2] - selectedRect[0] + 1),
48            // Y coordinate
49            selectedRect[1] + random.nextInt(selectedRect[3] - selectedRect[1] + 1)
50        };
51    }
52}
53
1#include <vector>
2#include <algorithm>
3#include <cstdlib>
4#include <ctime>
5
6using std::vector;
7using std::lower_bound;
8using std::srand;
9using std::rand;
10using std::time;
11
12class Solution {
13private:
14    vector<int> prefixSums;          // Stores the cumulative area sums of the rectangles.
15    vector<vector<int>> rectangles;  // Stores the list of input rectangles.
16
17public:
18    // Constructor that initializes the prefix sums and seeds the random number generator.
19    Solution(vector<vector<int>>& rects) {
20        rectangles = rects; // Store a copy of the rectangles array.
21        int numRectangles = rectangles.size();
22        prefixSums.resize(numRectangles + 1, 0);
23
24        // Calculate the cumulative area of rectangles to use for weighted random selection.
25        for (int i = 0; i < numRectangles; ++i) {
26            // Calculate the area of the rectangle and add it to the cumulative sum.
27            prefixSums[i + 1] = prefixSums[i] + 
28                                (rectangles[i][2] - rectangles[i][0] + 1) * 
29                                (rectangles[i][3] - rectangles[i][1] + 1);
30        }
31      
32        // Seed the random number generator with the current time.
33        srand(static_cast<unsigned int>(time(nullptr)));
34    }
35
36    // Picks a random point uniformly from the total area covered by rectangles.
37    vector<int> pick() {
38        // Choose a random value from 1 to the total area inclusive.
39        int target = 1 + rand() % prefixSums.back();
40      
41        // Find the rectangle that will contain the point.
42        int idx = static_cast<int>(lower_bound(prefixSums.begin(), prefixSums.end(), target) - prefixSums.begin()) - 1;
43      
44        // Get the rectangle information.
45        auto& rect = rectangles[idx];
46      
47        // Pick a random point within the chosen rectangle.
48        int x = rect[0] + rand() % (rect[2] - rect[0] + 1);
49        int y = rect[1] + rand() % (rect[3] - rect[1] + 1);
50      
51        return {x, y}; // Return the random point as a 2D vector.
52    }
53};
54
55// The following lines are provided for context and to illustrate usage.
56// This code would typically reside in a separate function and not within the class itself.
57// Solution* obj = new Solution(rects);
58// vector<int> param_1 = obj->pick();
59
1// The equivalent of the C++ vector in TypeScript is Array.
2let prefixSums: number[]; // Stores the cumulative area sums of the rectangles.
3let rectangles: number[][]; // Stores the list of input rectangles.
4
5// Function that initializes the prefix sums. Equivalent to the constructor in the C++ version.
6function initialize(rects: number[][]) {
7    rectangles = rects; // Store a copy of the rectangles array.
8    let numRectangles = rectangles.length;
9    prefixSums = new Array(numRectangles + 1).fill(0);
10
11    // Calculate the cumulative area of rectangles to use for weighted random selection.
12    for (let i = 0; i < numRectangles; ++i) {
13        // Calculate the area of the rectangle and add it to the cumulative sum.
14        prefixSums[i + 1] = prefixSums[i] +
15                            (rectangles[i][2] - rectangles[i][0] + 1) * 
16                            (rectangles[i][3] - rectangles[i][1] + 1);
17    }
18
19    // Seed the random number generator.
20    // Note: unlike C++, TypeScript's random number generator does not need to be seeded.
21}
22
23// Picks a random point uniformly from the total area covered by rectangles.
24function pick(): number[] {
25    // Choose a random value from 1 to the total area inclusive.
26    let target = 1 + Math.floor(Math.random() * prefixSums[prefixSums.length - 1]);
27  
28    // Find the rectangle that will contain the point.
29    let idx = prefixSums.findIndex(sum => sum >= target) - 1;
30  
31    // Get the rectangle information.
32    let rect = rectangles[idx];
33  
34    // Pick a random point within the chosen rectangle.
35    let x = rect[0] + Math.floor(Math.random() * (rect[2] - rect[0] + 1));
36    let y = rect[1] + Math.floor(Math.random() * (rect[3] - rect[1] + 1));
37  
38    return [x, y]; // Return the random point as a 2D array.
39}
40
41// Example usage:
42// initialize(rects);
43// let point = pick();
44// console.log(point);
45
Not Sure What to Study? Take the 2-min Quiz๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

Time Complexity:

  • __init__ method:

    • The method goes through each rectangle and calculates its area, which is done in O(1) time for each rectangle.
    • This results in an overall time complexity of O(n) for the __init__ method, where n is the number of rectangles.

  • pick method:

    • The pick method generates a random integer with random.randint, which is O(1) in time complexity.
    • It then uses bisect_left to find the appropriate rectangle which takes O(log n) time, where n is the number of rectangles.
    • Finally, generating a random point within the rectangle is again O(1).
    • Therefore, the time complexity of the pick method is O(log n).

Space Complexity

  • The additional space used by an instance of the Solution class is for storing the cumulative sum of the areas in the self.s list and the list of rectangles self.rects.
    • Since self.s has one entry per rectangle, its space complexity is O(n) where n is the number of rectangles.
    • The self.rects stores n rectangles, and each rectangle has 4 integers, so the space taken by self.rects is also O(n).
    • Therefore, the total space complexity is O(n), dominated by the storage of the rectangles and the cumulative sum.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ