We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Random Point in Non-overlapping Rectangles

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each rectangle can be defined by its corners, allowing us to calculate the area covered by each rectangle.
  • The total area of all rectangles can be used to generate a weighted random selection.
  • Randomly selecting a rectangle based on its area allows for uniform distribution of points within the selected rectangle.
  • The range of coordinates for random selection is limited by the dimensions of the rectangles, which are constrained to a maximum width and height of 2000.

Space and Time Complexity

Time Complexity: O(1) for the pick method after initialization, which is O(n) where n is the number of rectangles. Space Complexity: O(n) for storing the areas of rectangles.

Solution

To solve this problem, we can utilize the following approach:

  1. Calculate the area of each rectangle and maintain a cumulative area list to facilitate weighted random selection.
  2. Generate a random number that corresponds to a point in the cumulative area.
  3. Identify which rectangle this random number falls into using binary search.
  4. Once a rectangle is selected, randomly choose a point within its bounds using uniform random selection.

Code Solutions

import random

class Solution:
    def __init__(self, rects):
        self.rects = rects
        self.areas = []
        total_area = 0
        
        for a, b, x, y in rects:
            area = (x - a) * (y - b)
            total_area += area
            self.areas.append(total_area)

    def pick(self):
        target = random.randint(1, self.areas[-1])
        # Binary search to find the rectangle
        left, right = 0, len(self.areas) - 1
        while left < right:
            mid = (left + right) // 2
            if self.areas[mid] < target:
                left = mid + 1
            else:
                right = mid
        # Select the rectangle defined by rects[left]
        a, b, x, y = self.rects[left]
        # Randomly pick a point within the selected rectangle
        return [random.randint(a, x - 1), random.randint(b, y - 1)]
← Back to All Questions