Leetcode Random Point in Non-overlapping Rectangles problem solution

In this Leetcode Random Point in Non-overlapping Rectangles problem solution 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.

Leetcode Random Point in Non-overlapping Rectangles problem solution in Python.

class Solution:

    def __init__(self, rects: List[List[int]]):
        self.ranges = ranges = [0]
        self.rects = rects
        for x1,y1,x2,y2 in rects:
            ranges.append( ranges[-1] + (y2-y1+1)*(x2-x1+1) )
    def pick(self) -> List[int]:
        ranges, rects = self.ranges, self.rects
        areaPt = random.randint(1,ranges[-1])
        x1,y1,x2,y2 = rects[bisect.bisect_left(ranges,areaPt)-1]
        return [random.randint(x1,x2), random.randint(y1,y2)]

Random Point in Non-overlapping Rectangles problem solution in Java.

class Solution {
    TreeMap<Integer, Integer> map;
    int size;
    int[][] rects;
    public Solution(int[][] rects) {
        map = new TreeMap<>();
        this.rects = rects;
        //rects[i] = [x1,y1,x2,y2]
        for(int i=0; i<rects.length; i++) {
            int[] rect = rects[i];
            map.put(size, i);
            size += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
        }
    }

    public int[] pick() {
        int ran = new Random().nextInt(size);
        int floorKey = map.floorKey(ran);
        int nth = ran - floorKey;
        return getCoordinate(rects[map.get(floorKey)], nth);
    }

    private int[] getCoordinate (int[] rect, int nth) {
        int x_length = rect[2] - rect[0] + 1;
        int y = nth / x_length;
        int x = nth % x_length;
        return new int[] {rect[0] + x, rect[1] + y};
    }
}

Problem solution in C++.

class Solution {
public:
    vector<int> np;
    vector<vector<int>> Rects;
    Solution(vector<vector<int>>& rects) {
        Rects = rects;
        for(auto rect : rects){
            int l1 = rect[2] - rect[0] + 1;
            int l2 = rect[3] - rect[1] + 1;
            int val = np.size() ? np.back() + (l1*l2) : l1*l2; 
            np.push_back(val);
        }
    }
    
    vector<int> pick() {
        int m = np.back();
        int r = rand() % m;
        auto it = upper_bound(np.begin(), np.end(), r);
        int rect = it - np.begin();  //end of step 1
        //step 2 begins
        vector<int> R = Rects[rect];
        int x = rand() % (R[2]-R[0]+1) + R[0];
        int y = rand() % (R[3]-R[1]+1) + R[1];
        return {x, y};
    }
};

Leetcode Random Point in Non-overlapping Rectangles problem solution in Python.

Random Point in Non-overlapping Rectangles problem solution in Java.

Problem solution in C++.

Leave a Reply