Leetcode 497. Random Point in Non-overlapping Rectangles

Problem Description:

This problem involves picking an integer point within given rectangles. A point is said to be an integer point if its coordinates are integers. A rectangle will be represented by its two diagonal points in the form [x1,y1,x2,y2]. The point [x1, y1] signifies the bottom-left corner of the rectangle, and [x2, y2] signifies the top-right corner. It's essential to consider the points on the perimeter of the rectangles.

Let's take an example to understand the problem:

Suppose, rects = [[5,5,6,6],[7,8,9,10]], it means we have two rectangles. One rectangle has its bottom-left corner at (5,5) and top-right corner at (6,6). The other rectangle has its bottom-left corner at (7,8) and top-right corner at (9,10).

Our task is to write a function 'pick' which randomly selects an integer point from the area covered by these rectangles.

Approach:

The problem can be solved using the prefix sum and binary search algorithms. Here's how:

1. First determine the area of each rectangle and prepare a prefix sum array.
2. Randomly select a number up to the total area of all the rectangles.
3. Use binary search to find the rectangle that will contain the point corresponding to the random number.
4. Randomly select a point within this rectangle.

Let's walk through a sample example to understand this better:

Suppose, we have rectangles rects = [[1,1,5,5],[7,8,9,10]]. The area of first rectangle is (5-1+1)(5-1+1) = 25 and that of second rectangle is (9-7+1)(10-8+1) = 9. The prefix sum array will look like [25, 34].

If we randomly select a number, say 15, it falls within the range of first rectangle (1 to 25). Hence, select a random point within this rectangle.

Solution:

Python

1
2python
3import random
4import bisect
5
6class Solution:
7
8    def __init__(self, rects):
9        self.rects = rects
10        self.ranges = self.compute_ranges(rects)
11
12    def compute_ranges(self, rects):
13        ranges = []
14        total = 0
15        for x1, y1, x2, y2 in rects:
16            total += (x2-x1+1) * (y2-y1+1)
17            ranges.append(total)
18        return ranges
19
20    def pick(self):
21        rand_int = random.randint(0, self.ranges[-1]-1)
22        rect_index = bisect.bisect_left(self.ranges, rand_int+1)
23        x1, y1, x2, y2 = self.rects[rect_index]
24        return [random.randint(x1, x2), random.randint(y1, y2)]

Java

1
2java
3class Solution {
4    private int[][] rects;
5    private int[] areas;
6    private int totalArea;
7    private Random rand = new Random(); 
8    // This is for generating random numbers
9
10    public Solution(int[][] rects) {
11        this.rects = rects;
12        areas = new int[rects.length];
13        int total = 0;
14        
15        for (int i = 0; i < rects.length; i++) {
16            total += ((rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1));
17            areas[i] = total;
18        }
19        
20        totalArea = total;
21    }
22    
23    public int[] pick() {
24        int randInt = rand.nextInt(totalArea);
25        
26        int left = 0;
27        int right = rects.length - 1;
28        int index = right;
29        
30        while (left <= right) {
31            int mid = left + (right-left)/2;
32            if (randInt >= areas[mid])
33                left = mid + 1;
34            else {
35                right = mid - 1;
36                index = mid;
37            }
38        }
39        
40        int[] rect = rects[index];
41        int x = rand.nextInt(rect[2] - rect[0] + 1) + rect[0];
42        int y = rand.nextInt(rect[3] - rect[1] + 1) + rect[1];
43        return new int[] { x, y };
44    }
45}

Here, we are using the binary search and random functions of Java. The Solution function calculates the total area of the rectangles. The pick function generates a random integer within the total area, and then picks the rectangle and the point within it.## JavaScript

1
2javascript
3class Solution {
4    constructor(rects) {
5        this.rects = rects;
6        this.prefixSums = this.computePrefixSums(rects);
7        this.totalSum = this.prefixSums[this.prefixSums.length - 1];
8    }
9    
10    computePrefixSums(rects) {
11        let sums = new Array(rects.length);
12        let total = 0;
13        
14        for(let i = 0; i < rects.length; i++) {
15            let rect = rects[i];
16            total += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
17            sums[i] = total;
18        }
19        
20        return sums;
21    }
22    
23    pick() {
24        let target = Math.ceil(Math.random() * this.totalSum);
25        
26        let low = 0;
27        let high = this.rects.length - 1;
28        
29        while(low < high) {
30            let mid = Math.floor((high - low) / 2) + low;
31            
32            if(this.prefixSums[mid] < target) {
33                low = mid + 1;
34            } else {
35                high = mid;
36            }
37        }
38        
39        let rect = this.rects[low];
40        let width = rect[2] - rect[0] + 1;
41        let height = rect[3] - rect[1] + 1;
42        let base = this.prefixSums[low] - width * height;
43        
44        let x = rect[0] + (target - base - 1) % width;
45        let y = rect[1] + Math.floor((target - base - 1) / width);
46        
47        return [x, y];
48    }
49}

In the JavaScript solution, the constructor function initializes the rects array and calculates the prefix sums for each rectangle. The computePrefixSums function calculates the total area of each rectangle and stores it in the prefix sums array. In the pick function, we use the built-in Math.random function to generate a random number. It then implements a binary search over the range of prefix sums to find the rectangle that contains the randomly generated number. It then generates a random point within this rectangle.