Random Point in Non-overlapping Rectangles

Medium

Asked by:

18 views

Topics:

ArraysBinary Search

You are given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [a_i, b_i, x_i, y_i] indicates that (a_i, b_i) is the bottom-left corner point of the i^th rectangle and (x_i, y_i) is the top-right corner point of the i^th 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.

Note that an integer point is a point that has integer coordinates.

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 the space covered by one of the given rectangles.

Example 1:

Input
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
Output
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

Explanation
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]

Constraints:

1 <= rects.length <= 100
rects[i].length == 4
-10⁹ <= a_i < x_i <= 10⁹
-10⁹ <= b_i < y_i <= 10⁹
x_i - a_i <= 2000
y_i - b_i <= 2000
All the rectangles do not overlap.
At most 10⁴ calls will be made to pick.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the rectangles guaranteed to be non-overlapping, or could they intersect?
What is the range of possible values for the coordinates of the rectangles?
Can the rectangles have zero area (i.e., be a line or a point)?
How should the point be represented in the output? Specifically, what data type should I use and are integer or float coordinates expected?
Is the distribution of random points within each rectangle required to be uniform, or is some other weighting allowed?

Brute Force Solution

Approach

The brute force method for picking a random point within multiple rectangles works by first considering all possible points. Then, it checks if each point falls within one of the given rectangles.

Here's how the algorithm would work step-by-step:

Imagine covering the entire possible area with tiny, evenly spaced points.
Start checking each of these tiny points one by one.
For each point, check if it lies inside any of the rectangles.
If a point is inside a rectangle, we keep it as a possibility.
After checking all tiny points, we have a list of all the points that fall inside at least one rectangle.
Finally, we randomly pick one point from this list of valid points.

Code Implementation

import random

class Solution:
    def __init__(self, rectangles):
        self.rectangles = rectangles

    def pick(self):
        valid_points = []
        # Iterate through a dense grid of points
        for x_coordinate in range(-100, 101):
            for y_coordinate in range(-100, 101):
                # Check if current point is inside any rectangle
                for rectangle in self.rectangles:
                    x_minimum, y_minimum, x_maximum, y_maximum = rectangle
                    if x_minimum <= x_coordinate <= x_maximum and \
                       y_minimum <= y_coordinate <= y_maximum:
                        valid_points.append((x_coordinate, y_coordinate))
                        break

        # Prevent error when there are no valid points
        if not valid_points:
            return None

        # Select a random point from the collected valid points
        random_index = random.randint(0, len(valid_points) - 1)
        return valid_points[random_index]

Big(O) Analysis

Time Complexity

O(Area) – The brute force approach iterates through all possible points within the defined area. Let's consider 'Area' to represent the total number of potential points that need to be checked. For each of these points, we check if it lies within any of the rectangles. The complexity is directly proportional to the size of the total area covered with tiny points. Therefore, the time complexity is O(Area).

Space Complexity

O(A) – The brute force approach described constructs a list of all possible points that fall within at least one of the rectangles. In the worst case, every possible point within the bounding area defined by the rectangles could fall within at least one rectangle. Let A represent the area covered by the rectangles after considering the granularity of the 'tiny points'. The space complexity depends on the number of these valid points that we need to store in the list. The auxiliary space therefore depends on A, the number of valid points.

Optimal Solution

Approach

The goal is to pick a random point from a group of rectangles, giving larger rectangles a higher chance of being selected. We'll calculate the area of each rectangle to determine its 'weight,' then use these weights to make a random choice efficiently. This avoids generating tons of random points and checking if they're inside a rectangle.

Here's how the algorithm would work step-by-step:

First, figure out the area of each rectangle. This tells us how 'important' each rectangle is when we're picking a random point.
Next, create a 'running total' of these areas. This will help us quickly determine which rectangle our random point should come from.
Generate one random number. This random number should be smaller than the total area of all the rectangles combined.
Now, use the running totals to find the rectangle that 'contains' our random number. This is like finding which section of a weighted pie chart our random number falls into. The bigger the rectangle, the bigger its section of the pie.
Once we've identified the rectangle, generate random coordinates within that specific rectangle. Because we already chose the rectangle in a way that respects the areas, the final point is truly random across all the rectangles.
Return this random point.

Code Implementation

import random

class Solution:

    def __init__(self, rectangles):
        self.rectangles = rectangles
        self.areas = []
        self.total_area = 0
        for rectangle in rectangles:
            area = (rectangle[2] - rectangle[0] + 1) * (rectangle[3] - rectangle[1] + 1)
            self.total_area += area
            self.areas.append(self.total_area)

    def pick(self):
        # Generate a random number within the total area
        random_area = random.randint(1, self.total_area)

        # Binary search to find the rectangle containing the random area
        left_index = 0
        right_index = len(self.areas) - 1
        while left_index < right_index:
            middle_index = (left_index + right_index) // 2
            if self.areas[middle_index] < random_area:
                left_index = middle_index + 1
            else:
                right_index = middle_index

        # Pick random point within the selected rectangle
        rectangle_index = left_index
        x_min, y_min, x_max, y_max = self.rectangles[rectangle_index]

        # Generate random x and y coordinates within the rectangle
        random_x = random.randint(x_min, x_max)
        random_y = random.randint(y_min, y_max)

        return [random_x, random_y]

Big(O) Analysis

Time Complexity

O(n) – The dominant operations involve initializing the area array and calculating the cumulative area sums, both of which iterate through the input list of rectangles of size n exactly once. The binary search, although present in the `pick` function, has a time complexity of O(log n). However, since the initialization step which takes O(n) is done only once and pick() may be called multiple times, the overall complexity is dominated by the initial processing of rectangles. Therefore the overall time complexity is O(n) for initialization and O(log n) per pick, but considered together it is O(n + k log n) where k is the number of picks. If k is less than n then the overall complexity is O(n), if k > n then the complexity is O(k log n).

Space Complexity

O(N) – The algorithm creates a 'running total' of areas, which requires storing these cumulative sums in an auxiliary array. The size of this array is directly proportional to the number of rectangles, N, where N is the number of rectangles provided in the input. Therefore, the auxiliary space used grows linearly with the input size N. The storage of the areas, the random number and the coordinates within a given rectangle all use constant space.

Edge Cases

Case	How to Handle
Empty input list of rectangles	Return null or throw an exception, as there are no rectangles to sample from.
Single rectangle in the input list	The selection logic should correctly sample from this single rectangle.
Very large number of rectangles, approaching memory limits	Ensure the precomputed area sums use appropriate data types to prevent overflow, and consider alternative data structures if memory becomes a bottleneck.
Rectangles with zero area (e.g., same x1 and x2, or same y1 and y2)	Exclude these rectangles from the weighted probability calculations to avoid division by zero or incorrect sampling.
Rectangles with large area differences (some are much larger than others)	The weighted sampling algorithm should still function correctly, ensuring that larger rectangles have a proportionally higher probability of being selected.
Integer overflow when calculating area or cumulative area (especially with large coordinate values)	Use long data types for area and cumulative area calculations to prevent integer overflow.
Random number generator producing non-uniform distribution (although unlikely)	Verify the underlying random number generator provides a statistically uniform distribution to ensure fair sampling.
All rectangles are located at the same location	Code should handle same location but differing dimensions, or same dimensions but same location; it functions as intended because we are summing weights.

Empty input list of rectangles

How to Handle:

Return null or throw an exception, as there are no rectangles to sample from.

Single rectangle in the input list

How to Handle:

The selection logic should correctly sample from this single rectangle.

Very large number of rectangles, approaching memory limits

How to Handle:

Ensure the precomputed area sums use appropriate data types to prevent overflow, and consider alternative data structures if memory becomes a bottleneck.

Rectangles with zero area (e.g., same x1 and x2, or same y1 and y2)

How to Handle:

Exclude these rectangles from the weighted probability calculations to avoid division by zero or incorrect sampling.

Rectangles with large area differences (some are much larger than others)

How to Handle:

The weighted sampling algorithm should still function correctly, ensuring that larger rectangles have a proportionally higher probability of being selected.

Integer overflow when calculating area or cumulative area (especially with large coordinate values)

How to Handle:

Use long data types for area and cumulative area calculations to prevent integer overflow.

Random number generator producing non-uniform distribution (although unlikely)

How to Handle:

Verify the underlying random number generator provides a statistically uniform distribution to ensure fair sampling.

All rectangles are located at the same location

How to Handle:

Code should handle same location but differing dimensions, or same dimensions but same location; it functions as intended because we are summing weights.