algoadvance

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 coordinate of the bottom-left corner, and (xi, yi) is the coordinate of the top-right corner of the ith rectangle. Design an algorithm to pick a random integer point inside one of the given rectangles. A point on the perimeter of a rectangle is considered to be inside it.

Implement the Solution class:

• Solution(int[][] rects) Initializes the object with the given rectangles rects.
• int[] pick() Returns a random integer point [u, v] inside one of the given rectangles.

Clarifying Questions

1. What kind of distribution should the random point follow?
   • The random point should be uniformly distributed across all the rectangles.
2. Can the rectangles be degenerate (zero area)?
   • The description implies that all rectangles have non-zero area as they are explicitly called out as non-overlapping.
3. Will I need to handle any invalid inputs, such as malformed rectangles?
   • No, assume the input is always valid as per the problem statement constraints.

Strategy

1. Precompute Areas:
   • Calculate the area (number of points) of each rectangle.
   • Maintain a cumulative distribution of areas to facilitate weighted random selection of a rectangle.
2. Selecting a Rectangle:
   • Using the cumulative distribution, pick a rectangle based on the weight of its area. This ensures the probability of selecting any point is uniform across all points in all rectangles.
3. Selecting a Point Inside a Rectangle:
   • Once a rectangle is selected, pick a random point within the bounds of the rectangle.

Code

Here’s the code to implement this strategy:

import random
import itertools

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        # Compute cumulative weights for the areas of the rectangles
        self.weights = []
        current_area = 0
        
        for rect in rects:
            # Calculate number of points in this rectangle
            x1, y1, x2, y2 = rect
            area = (x2 - x1 + 1) * (y2 - y1 + 1)
            current_area += area
            self.weights.append(current_area)
    
    def pick(self) -> List[int]:
        # Pick a random point choosing rectangle based on area-weighted distribution
        target = random.randint(1, self.weights[-1])
        
        # Binary search to find the correct rectangle
        left, right = 0, len(self.weights) - 1
        while left < right:
            mid = left + (right - left) // 2
            if target > self.weights[mid]:
                left = mid + 1
            else:
                right = mid
        
        # 'left' should now indicate the selected rectangle
        x1, y1, x2, y2 = self.rects[left]
        
        # Pick a random point within this rectangle
        random_x = random.randint(x1, x2)
        random_y = random.randint(y1, y2)
        
        return [random_x, random_y]

Time Complexity

• Initialization (__init__ method): O(n), where n is the number of rectangles since we need to compute the cumulative distribution of areas.
• Selection (pick method): O(log n) to select the rectangle using binary search, and O(1) to pick a point inside the rectangle.

This solution is efficient and well-suited for the problem constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?