Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/497.html

497. Random Point in Non-overlapping Rectangles (Medium)

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

  1. An integer point is a point that has integer coordinates. 
  2. A point on the perimeter of a rectangle is included in the space covered by the rectangles. 
  3. ith rectangle = rects[i][x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
  4. length and width of each rectangle does not exceed 2000.
  5. 1 <= rects.length <= 100
  6. pick return a point as an array of integer coordinates [p_x, p_y]
  7. pick is called at most 10000 times.

Example 1:

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2:

Input: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

 

Related Topics:
Binary Search, Random

Similar Questions:

// OJ: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
// Time:
//      Solution: O(N)
//      pick: O(logN)
// Space: O(N)
class Solution {
    vector<vector<int>> A;
    vector<int> size;
    int total = 0;
public:
    Solution(vector<vector<int>>& rects) : A(rects) {
        for (auto &r : A) size.push_back(total += (r[3] - r[1] + 1) * (r[2] - r[0] + 1));
    }
    vector<int> pick() {
        int r = rand() % total;
        int i = upper_bound(begin(size), end(size), r) - begin(size);
        r -= i > 0 ? size[i - 1] : 0;
        int w = A[i][3] - A[i][1] + 1;
        return { A[i][0] + r / w, A[i][1] + r % w };
    }
};
  • class Solution {
        int rectsCount;
        int[][] rects;
        int[] accumulatedPoints;
        int pointsCount;
    
        public Solution(int[][] rects) {
            rectsCount = rects.length;
            this.rects = rects;
            accumulatedPoints = new int[rectsCount];
            for (int i = 0; i < rectsCount; i++) {
                int[] rect = rects[i];
                int points = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
                accumulatedPoints[i] = points;
                pointsCount += points;
            }
            for (int i = 1; i < rectsCount; i++)
                accumulatedPoints[i] += accumulatedPoints[i - 1];
        }
        
        public int[] pick() {
            int pointsPosition = (int) (Math.random() * pointsCount);
            int index = 0;
            for (int i = 0; i < rectsCount; i++) {
                if (accumulatedPoints[i] > pointsPosition) {
                    index = i;
                    break;
                }
            }
            int[] rect = rects[index];
            int xMin = rect[0], xMax = rect[2];
            int yMin = rect[1], yMax = rect[3];
            int randomX = xMin + (int) (Math.random() * (xMax - xMin + 1));
            int randomY = yMin + (int) (Math.random() * (yMax - yMin + 1));
            int[] randomPoint = {randomX, randomY};
            return randomPoint;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(rects);
     * int[] param_1 = obj.pick();
     */
    ############
    
    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();
     */
    
  • // OJ: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
    // Time:
    //      Solution: O(N)
    //      pick: O(logN)
    // Space: O(N)
    class Solution {
        vector<vector<int>> A;
        vector<int> size;
        int total = 0;
    public:
        Solution(vector<vector<int>>& rects) : A(rects) {
            for (auto &r : A) size.push_back(total += (r[3] - r[1] + 1) * (r[2] - r[0] + 1));
        }
        vector<int> pick() {
            int r = rand() % total;
            int i = upper_bound(begin(size), end(size), r) - begin(size);
            r -= i > 0 ? size[i - 1] : 0;
            int w = A[i][3] - A[i][1] + 1;
            return { A[i][0] + r / w, A[i][1] + r % w };
        }
    };
    
  • class Solution:
        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)]
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(rects)
    # param_1 = obj.pick()
    
    ############
    
    class Solution(object):
    
        def __init__(self, rects):
            """
            :type rects: List[List[int]]
            """
            self.rects = rects
            self.N = len(rects)
            areas = [(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects]
            self.preSum = [0] * self.N
            self.preSum[0] = areas[0]
            for i in range(1, self.N):
                self.preSum[i] = self.preSum[i - 1] + areas[i]
            self.total = self.preSum[-1]
    
        def pickRect(self):
            rand = random.randint(0, self.total - 1)
            return bisect.bisect_right(self.preSum, rand)
    
        def pickPoint(self, rect):
            x1, y1, x2, y2 = rect
            x = random.randint(x1, x2)
            y = random.randint(y1, y2)
            return x, y
            
        def pick(self):
            """
            :rtype: List[int]
            """
            rectIndex = self.pickRect()
            rect = self.rects[rectIndex]
            return self.pickPoint(rect)
            
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(rects)
    # param_1 = obj.pick()
    
  • type Solution struct {
    	s     []int
    	rects [][]int
    }
    
    func Constructor(rects [][]int) Solution {
    	n := len(rects)
    	s := make([]int, n+1)
    	for i, v := range rects {
    		s[i+1] = s[i] + (v[2]-v[0]+1)*(v[3]-v[1]+1)
    	}
    	return Solution{s, rects}
    }
    
    func (this *Solution) Pick() []int {
    	n := len(this.rects)
    	v := 1 + rand.Intn(this.s[len(this.s)-1])
    	left, right := 0, n
    	for left < right {
    		mid := (left + right) >> 1
    		if this.s[mid] >= v {
    			right = mid
    		} else {
    			left = mid + 1
    		}
    	}
    	rect := this.rects[left-1]
    	x, y := rect[0]+rand.Intn(rect[2]-rect[0]+1), rect[1]+rand.Intn(rect[3]-rect[1]+1)
    	return []int{x, y}
    }
    

All Problems

All Solutions