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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Random Point in Non-overlapping Rectangles

Number: 914

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Design an algorithm to pick a random integer point inside the space covered by one of the given non-overlapping axis-aligned rectangles. Each rectangle is defined by its bottom-left corner (a, b) and its top-right corner (x, y). Every integer point inside a rectangle, including those on its perimeter, should be equally likely to be chosen.

Key Insights

  • Calculate the number of integer points inside each rectangle as (x - a + 1) * (y - b + 1).
  • Build a prefix sum array over these counts to enable weighted random selection of a rectangle.
  • Use binary search on the prefix sum array to quickly identify which rectangle a randomly generated integer point belongs to.
  • Once a rectangle is selected, randomly pick a point within its boundaries.

Space and Time Complexity

Time Complexity:

  • Preprocessing: O(n) where n is the number of rectangles.
  • Each pick operation: O(log n) due to the binary search.

Space Complexity:

  • O(n) for storing the prefix sums and the input rectangles.

Solution

The solution involves two main steps:

  1. Preprocess the list of rectangles by calculating and storing a cumulative count of integer points. This cumulative or prefix sum array allows us to determine which rectangle a randomly selected point falls into.
  2. For each call to pick(), generate a random integer in the range [1, total number of points]. Use binary search on the prefix sum array to determine the rectangle corresponding to that random integer. Then, pick a random x-coordinate and a random y-coordinate within that rectangle’s boundaries. This approach guarantees that each integer point across all rectangles is selected with equal probability.

Code Solutions

import random
import bisect

class Solution:
    def __init__(self, rects):
        # Save the rectangles list
        self.rects = rects
        # Create an array to store the cumulative number of points
        self.prefix = []
        total = 0
        # For each rectangle compute the number of integer points it contains
        for a, b, x, y in rects:
            # Number of integer points in the rectangle
            count = (x - a + 1) * (y - b + 1)
            total += count
            self.prefix.append(total)
    
    def pick(self):
        # Generate a random integer in range [1, total number of points]
        target = random.randint(1, self.prefix[-1])
        # Use binary search to find the rectangle index corresponding to target
        rect_index = bisect.bisect_left(self.prefix, target)
        a, b, x, y = self.rects[rect_index]
        # Compute the width of the rectangle (number of integer x positions)
        width = x - a + 1
        # Generate a random index offset within the rectangle's point count
        offset = target - (self.prefix[rect_index - 1] if rect_index else 0) - 1
        # Determine the x and y coordinate from the offset
        dx = offset % width
        dy = offset // width
        return [a + dx, b + dy]
← Back to All Questions