Problem Description

You are given an array of non-overlapping axis-aligned rectangles where each rectangle is defined by four coordinates: [a_i, b_i, x_i, y_i]. The point (a_i, b_i) represents the bottom-left corner and (x_i, y_i) represents the top-right corner of the i-th rectangle.

Your task is to design a data structure that can randomly pick an integer point from the space covered by all the rectangles. The key requirements are:

1. Integer Points Only: You must return points with integer coordinates (e.g., [3, 5] not [3.5, 5.2])

2. Inclusive Boundaries: Points on the perimeter of rectangles are considered inside the rectangle

3. Uniform Distribution: Every integer point within any rectangle should have an equal probability of being selected

You need to implement a Solution class with two methods:

• __init__(rects): Initialize the data structure with the given rectangles
• pick(): Return a random integer point [u, v] that lies inside one of the rectangles

Example: If you have a rectangle [1, 1, 3, 3], the valid integer points would be:

• (1,1), (1,2), (1,3)
• (2,1), (2,2), (2,3)
• (3,1), (3,2), (3,3)

That's 9 total points (a 3×3 grid), and each should have a 1/9 probability of being selected when this is the only rectangle.

The challenge is handling multiple rectangles of different sizes while maintaining uniform probability across all valid points in all rectangles.

Intuition

The key insight is that we need to ensure every integer point across all rectangles has an equal probability of being selected. If we simply picked a random rectangle first and then a random point within it, larger rectangles would have their points selected less frequently than smaller rectangles.

Consider two rectangles: one with 100 integer points and another with just 10 integer points. If we pick each rectangle with 50% probability, then each point in the small rectangle has a 5% chance of being selected (50% × 1/10), while each point in the large rectangle only has a 0.5% chance (50% × 1/100). This violates the uniform distribution requirement.

The solution is to use weighted random selection based on the number of integer points in each rectangle. We need to:

1. Calculate how many integer points each rectangle contains. For a rectangle [x1, y1, x2, y2], the number of integer points is (x2 - x1 + 1) × (y2 - y1 + 1). The +1 is crucial because the boundaries are inclusive.

2. Build a cumulative sum array where s[i] represents the total number of integer points in rectangles 0 through i. This creates ranges where rectangle i "owns" the integers from s[i-1] + 1 to s[i].

3. To pick a point, we generate a random number between 1 and the total number of points across all rectangles. We then use binary search to find which rectangle this number falls into based on our cumulative sum array.

4. Once we know which rectangle to use, we can uniformly pick a random integer point within that specific rectangle using random.randint(x1, x2) and random.randint(y1, y2).

This approach ensures that if there are 110 total integer points (100 in the first rectangle and 10 in the second), each individual point has exactly a 1/110 probability of being selected, regardless of which rectangle it belongs to.

Solution Approach

The implementation uses a prefix sum array combined with binary search to efficiently select rectangles based on their point counts.

Initialization (__init__ method):

1. Store the rectangles array for later use: self.rects = rects

2. Create a prefix sum array self.s with the same length as the number of rectangles. Each element s[i] will store the cumulative count of all integer points from rectangle 0 to rectangle i.

3. For each rectangle [x1, y1, x2, y2]:

   • Calculate the number of integer points: (x2 - x1 + 1) * (y2 - y1 + 1)
   • Add this count to the previous cumulative sum: self.s[i] = self.s[i - 1] + point_count
   • Note: When i = 0, self.s[i - 1] gives us self.s[-1] which Python interprets as the last element, but since we initialized with zeros, this works correctly

Pick Method (pick):

1. Generate a random integer v between 1 and the total number of points (stored in self.s[-1]). This represents selecting the v-th point among all points.

2. Use bisect_left(self.s, v) to find which rectangle contains the v-th point:

   • bisect_left returns the leftmost position where v could be inserted to keep the array sorted
   • This gives us the index of the rectangle that "owns" this point number
   • For example, if s = [0, 9, 19, 25] and v = 15, bisect_left returns index 2, meaning the point is in rectangle 2

3. Retrieve the selected rectangle's coordinates: x1, y1, x2, y2 = self.rects[idx]

4. Uniformly select a random integer point within this rectangle:

   • Random x-coordinate: random.randint(x1, x2)
   • Random y-coordinate: random.randint(y1, y2)
   • Return [x, y]

Time Complexity:

• Initialization: O(n) where n is the number of rectangles
• Pick: O(log n) for binary search plus O(1) for random point generation

Space Complexity:

• O(n) to store the rectangles and prefix sum array

Example Walkthrough

Let's walk through a concrete example with three rectangles to illustrate how the solution works:

Given rectangles:

• Rectangle 0: [1, 1, 2, 3]
• Rectangle 1: [3, 2, 5, 3]
• Rectangle 2: [2, 5, 3, 5]

Step 1: Calculate integer points in each rectangle

For Rectangle 0 [1, 1, 2, 3]:

• Width: 2 - 1 + 1 = 2 points
• Height: 3 - 1 + 1 = 3 points
• Total points: 2 × 3 = 6 points
• These are: (1,1), (1,2), (1,3), (2,1), (2,2), (2,3)

For Rectangle 1 [3, 2, 5, 3]:

• Width: 5 - 3 + 1 = 3 points
• Height: 3 - 2 + 1 = 2 points
• Total points: 3 × 2 = 6 points
• These are: (3,2), (3,3), (4,2), (4,3), (5,2), (5,3)

For Rectangle 2 [2, 5, 3, 5]:

• Width: 3 - 2 + 1 = 2 points
• Height: 5 - 5 + 1 = 1 point
• Total points: 2 × 1 = 2 points
• These are: (2,5), (3,5)

Step 2: Build prefix sum array

Starting with s = [0, 0, 0]:

• s[0] = 0 + 6 = 6 (Rectangle 0 has 6 points)
• s[1] = 6 + 6 = 12 (Rectangle 0 + Rectangle 1 = 12 points)
• s[2] = 12 + 2 = 14 (All rectangles = 14 points total)

Final prefix sum array: s = [6, 12, 14]

This means:

• Points 1-6 belong to Rectangle 0
• Points 7-12 belong to Rectangle 1
• Points 13-14 belong to Rectangle 2

Step 3: Simulate picking a random point

Let's say random.randint(1, 14) returns 10.

Using bisect_left(s, 10):

• We search for where 10 would fit in [6, 12, 14]
• Since 10 > 6 but 10 ≤ 12, bisect_left returns index 1
• This means we select Rectangle 1: [3, 2, 5, 3]

Now we pick a random point within Rectangle 1:

• Random x: random.randint(3, 5) → let's say it returns 4
• Random y: random.randint(2, 3) → let's say it returns 3
• Return [4, 3]

Probability verification: Each of the 14 integer points has exactly 1/14 probability of being selected:

• Rectangle 0's 6 points: Each has probability (6/14) × (1/6) = 1/14 ✓
• Rectangle 1's 6 points: Each has probability (6/14) × (1/6) = 1/14 ✓
• Rectangle 2's 2 points: Each has probability (2/14) × (1/2) = 1/14 ✓

The weighted selection ensures uniform distribution across all points regardless of which rectangle they belong to.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__: O(n) where n is the number of rectangles. The method iterates through all rectangles once to calculate the cumulative area sum.
• pick: O(log n) for the binary search using bisect_left to find the target rectangle, plus O(1) for generating random coordinates within the selected rectangle.

Space Complexity:

• O(n) where n is the number of rectangles. The solution stores:
  • self.rects: O(n) space to store the original rectangles
  • self.s: O(n) space to store the cumulative sum array of areas

The algorithm uses a weighted random selection approach where rectangles with larger areas have proportionally higher chances of being selected. The cumulative sum array enables efficient rectangle selection using binary search.

Common Pitfalls

1. Incorrect Binary Search Logic

The most common pitfall in this solution is misunderstanding how bisect_left works with the prefix sum array and random point index.

The Problem: The code has a critical bug in the pick method. After using bisect_left, there's unnecessary logic trying to "fix" the rectangle index:

if rectangle_index < len(self.prefix_sums) and self.prefix_sums[rectangle_index] < random_point_index:
    rectangle_index += 1

This is incorrect because:

• When random_point_index is between two prefix sum values, bisect_left returns the index of the larger value
• The additional adjustment can cause index out of bounds errors or select the wrong rectangle

The Fix: Use bisect_right (or bisect) instead, which naturally gives us the correct rectangle index:

def pick(self) -> List[int]:
    # Pick a random point index from 1 to total number of points
    random_point_index = random.randint(1, self.prefix_sums[-1])
  
    # Find which rectangle contains this point using binary search
    rectangle_index = bisect.bisect_right(self.prefix_sums, random_point_index - 1)
  
    # Get the selected rectangle's coordinates
    x1, y1, x2, y2 = self.rects[rectangle_index]
  
    # Pick a random point within the selected rectangle
    random_x = random.randint(x1, x2)
    random_y = random.randint(y1, y2)
  
    return [random_x, random_y]

2. Off-by-One Error in Point Counting

Developers often forget that both boundaries are inclusive when counting integer points.

The Problem: Incorrectly calculating points as (x2 - x1) * (y2 - y1) instead of (x2 - x1 + 1) * (y2 - y1 + 1).

Example: For rectangle [1, 1, 3, 3]:

• Wrong: (3-1) * (3-1) = 4 points
• Correct: (3-1+1) * (3-1+1) = 9 points

3. Random Range Selection Error

Using 0-based indexing for the random point selection instead of 1-based.

The Problem: Using random.randint(0, self.prefix_sums[-1] - 1) can cause issues with the binary search logic since the prefix sum array conceptually represents cumulative counts starting from 1.

The Fix: Stick with 1-based indexing: random.randint(1, self.prefix_sums[-1]) and adjust the binary search accordingly.