How do you solve Random Point in Non-overlapping Rectangles on LeetCode?

Random Point in Non-overlapping Rectangles (LeetCode #497) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(n) space complexity. Key insight: Using prefix sums allows efficient area management.

What is the brute force solution for Random Point in Non-overlapping Rectangles?

The brute force approach for Random Point in Non-overlapping Rectangles is Brute Force, with O(n²) time complexity and O(n) space complexity. In the brute-force approach, we can generate all possible integer points within the given rectangles and randomly select one. This is straightforward but inefficient, especially with larger rectangles. The optimal Optimal Solution approach improves this to O(log n).

What are the interview tips for Random Point in Non-overlapping Rectangles?

Explain your thought process clearly. Discuss the trade-offs of different approaches. Practice coding the solution under time constraints.

What are common mistakes when solving Random Point in Non-overlapping Rectangles?

Not considering the area of rectangles when picking random points. Failing to handle edge cases like overlapping rectangles.

#497

Random Point in Non-overlapping Rectangles

Medium

ArrayMathBinary SearchReservoir SamplingPrefix SumOrdered SetRandomizedPrefix SumBinary Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(n)	O(n)

💡

Intuition

Time O(log n)Space O(n)

The optimal approach uses a prefix sum to efficiently select a random point from the rectangles without generating all possible points. This allows us to handle larger rectangles and maintain a uniform distribution of points.

⚙️

Algorithm

3 steps

1Step 1: Calculate the area of each rectangle and maintain a prefix sum array of these areas.
2Step 2: Generate a random number up to the total area and determine which rectangle it falls into using binary search.
3Step 3: Randomly select a point within the chosen rectangle based on its coordinates.

solution.py25 lines

1import random
2
3class Solution:
4    def __init__(self, rects):
5        self.rects = rects
6        self.prefix_sum = []
7        total_area = 0
8        for a, b, x, y in rects:
9            area = (x - a + 1) * (y - b + 1)
10            total_area += area
11            self.prefix_sum.append(total_area)
12        self.total_area = total_area
13
14    def pick(self):
15        target = random.randint(1, self.total_area)
16        low, high = 0, len(self.prefix_sum) - 1
17        while low < high:
18            mid = (low + high) // 2
19            if self.prefix_sum[mid] < target:
20                low = mid + 1
21            else:
22                high = mid
23        rect = self.rects[low]
24        a, b, x, y = rect
25        return [random.randint(a, x), random.randint(b, y)]

ℹ

Complexity note: The time complexity is O(log n) due to the binary search on the prefix sum array to find the rectangle. The space complexity is O(n) for storing the prefix sums.

1Using prefix sums allows efficient area management.
2Binary search helps quickly identify which rectangle to pick from.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.