LeetCode 497: Random Point in Non-overlapping Rectangles Solution in Python – A Step-by-Step Guide

What Is LeetCode 497: Random Point in Non-overlapping Rectangles?

In LeetCode 497: Random Point in Non-overlapping Rectangles, you’re tasked with implementing a class that picks a uniform random integer point within a set of non-overlapping rectangles defined by rects, an array where each element [x1, y1, x2, y2] represents a rectangle from (x1, y1) bottom-left to (x2, y2) top-right. The class has a method pick() that returns a random [x, y] point, ensuring every point across all rectangles has an equal probability. For example, with rects = [[1,1,5,5]], pick() might return [2, 3], and with rects = [[1,1,5,5], [6,6,8,8]], it could return [7, 7] or [3, 4], weighted by area. It’s like scattering treasure pins across disjoint zones, making sure each spot gets a fair shot.

Problem Statement

• Input:
• Solution(rects: List[List[int]])—initialize with rectangles [[x1, y1, x2, y2]].
• pick()—generate a random point.
• Output: List[int]—[x, y] random integer point within some rectangle.
• Rules:
• Rectangles are non-overlapping.
• Point must be within bounds [x1, y1] to [x2, y2] (inclusive).
• Uniform distribution: each point has equal probability.

Constraints

• \( 1 \leq rects.length \leq 100 \).
• \( rects[i].length == 4 \).
• \( -10^9 \leq x1 < x2 \leq 10^9 \).
• \( -10^9 \leq y1 < y2 \leq 10^9 \).
• \( x2 - x1 < 10^9 \), \( y2 - y1 < 10^9 \).
• Up to 10^4 calls to pick().

Examples to Get Us Started

• Input: ["Solution","pick","pick"], [[[1,1,5,5]],[],[]]
• Output: [null,[4,3],[2,5]] (Random points in [1,1,5,5]).
• Input: ["Solution","pick"], [[[1,1,5,5],[6,6,8,8]],[],[]]
• Output: [null,[7,7]] (Random point across both rectangles).

Understanding the Problem: Pinning the Treasure

To solve LeetCode 497: Random Point in Non-overlapping Rectangles in Python, we need to pick a uniform random integer point across all rectangles in rects, where each point’s probability is proportional to the total number of points (total area). A naive approach—iterating all points and picking one—could be O(T) (T = total points), infeasible for large areas up to 10^9. The key? Use prefix sums of rectangle areas with binary search to select a rectangle in O(log n) time (n = number of rectangles), then pick a point within it, achieving O(log n) per pick. We’ll explore:

• Best Solution (Prefix Sum with Binary Search): O(n) init, O(log n) per pick, O(n) space—fast and optimal.
• Alternative Solution (Brute Force Area Iteration): O(n + T) init, O(1) per pick, O(T) space—simple but slow.

Let’s dive into the prefix sum solution—it’s the hunter’s precise compass we need.

Best Solution: Prefix Sum with Binary Search

Why This Is the Best Solution

The prefix sum with binary search approach is the top pick because it’s O(n) time to initialize (n = number of rectangles) and O(log n) per pick() call, with O(n) space, efficiently selecting a random point by precomputing area prefix sums and using binary search to pick a rectangle proportional to its area, then randomly choosing a point within it. It avoids enumerating all points, leveraging weighted random selection. It’s like marking treasure zones by size, then spinning a wheel to land on one and picking a spot—smart and swift!

How It Works

Here’s the strategy:

• Step 1: Initialize:
• Compute area of each rectangle: \( (x2 - x1 + 1) * (y2 - y1 + 1) \).
• Build prefix sum array of total points up to each rectangle.
• Store rects and prefix sums.
• Step 2: Pick method:
• Generate random point index (0 to total points - 1).
• Binary search prefix sums to find rectangle (index where sum ≥ point).
• Pick random x, y within that rectangle’s bounds.
• Step 3: Return [x, y].
• Why It Works:
• Prefix sums weight rectangles by area, ensuring uniform probability.
• Binary search finds rectangle in O(log n), random choice within is O(1).

Step-by-Step Example

Example: rects = [[1,1,5,5]]

• Init:
• Area = (5-1+1) * (5-1+1) = 25.
• Prefix sums = [25].
• Total points = 25.
• Pick:
• Rand(0, 24) = 14.
• Binary search: 14 < 25, rect 0.
• Rand x: 1 + (14 // 5) = 3, y: 1 + (14 % 5) = 5.
• Result: [3, 5].

Example: rects = [[1,1,2,2],[3,3,4,4]]

• Init:
• Area1 = 4, Area2 = 4.
• Prefix sums = [4, 8].
• Total = 8.
• Pick:
• Rand(0, 7) = 5.
• Binary search: 4 ≤ 5 < 8, rect 1.
• Offset = 5 - 4 = 1, x = 3 + (1 // 2) = 3, y = 3 + (1 % 2) = 4.
• Result: [3, 4].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

import random
import bisect

class Solution:
    def __init__(self, rects: List[List[int]]):
        # Step 1: Initialize
        self.rects = rects
        self.points = []
        total = 0
        for x1, y1, x2, y2 in rects:
            area = (x2 - x1 + 1) * (y2 - y1 + 1)
            total += area
            self.points.append(total)
        self.total_points = total

    def pick(self) -> List[int]:
        # Step 2: Pick random point index
        point = random.randint(0, self.total_points - 1)

        # Binary search to find rectangle
        idx = bisect.bisect_left(self.points, point + 1)
        x1, y1, x2, y2 = self.rects[idx]

        # Offset within rectangle
        offset = point - (self.points[idx - 1] if idx > 0 else 0)
        width = x2 - x1 + 1
        x = x1 + (offset // (y2 - y1 + 1))
        y = y1 + (offset % (y2 - y1 + 1))

        # Step 3: Return point
        return [x, y]

• Line 6-14: Init:
• Store rects, compute prefix sums of points.
• Total points = sum of all areas.
• Line 17-25: Pick:
• Rand point index.
• Binary search for rectangle (first sum > point).
• Compute x, y from offset within rect.
• Time Complexity: O(n) init, O(log n) per pick.
• Space Complexity: O(n)—prefix sums array.

It’s like a treasure-pin dropper!

Alternative Solution: Brute Force Area Iteration

Why an Alternative Approach?

The brute force area iteration—O(n + T) init (T = total points), O(1) per pick, O(T) space—builds a list of all possible points across rectangles, then picks one randomly. It’s slow to initialize and memory-heavy but intuitive, like listing every treasure spot and throwing a dart. Good for small total areas or learning!

How It Works

• Step 1: Init:
• Generate all points in all rectangles.
• Store in list.
• Step 2: Pick:
• Randomly select index from list.
• Step 3: Return point.

Step-by-Step Example

Example: rects = [[1,1,2,2]]

• Init: Points = [[1,1], [1,2], [2,1], [2,2]] (4 points).
• Pick: Rand(0, 3) = 2 → [2, 1].
• Result: [2, 1].

Code for Brute Force

import random

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.points = []
        for x1, y1, x2, y2 in rects:
            for x in range(x1, x2 + 1):
                for y in range(y1, y2 + 1):
                    self.points.append([x, y])

    def pick(self) -> List[int]:
        return random.choice(self.points)

• Line 5-9: Build list of all points.
• Line 12: Pick random point.
• Time Complexity: O(n + T) init, O(1) pick.
• Space Complexity: O(T)—all points stored.

It’s a slow treasure lister!

Comparing the Two Solutions

• Prefix Sum (Best):
• Pros: O(n) init, O(log n) pick, scalable.
• Cons: O(n) space, complex.
• Brute Force (Alternative):
• Pros: O(1) pick, simple.
• Cons: O(n + T) init, O(T) space, slow setup.

Prefix sum wins for efficiency.

Edge Cases and Examples

• Single point: [[1,1,1,1]] → [1,1].
• Large area: Handles up to 10^9 bounds.
• One rect: Uniform within bounds.

Prefix sum handles all perfectly.

Complexity Recap

• Prefix Sum: Init O(n), Pick O(log n), Space O(n).
• Brute Force: Init O(n + T), Pick O(1), Space O(T).

Prefix sum’s the champ.

Key Takeaways

• Prefix Sum: Weight and search.
• Brute Force: List all points.
• Python Tip: Random rocks—see [Python Basics](/python/basics).

Final Thoughts: Drop That Pin

LeetCode 497: Random Point in Non-overlapping Rectangles in Python is a treasure-dropping random quest. Prefix sum with binary search is your fast compass, while brute force is a slow mapmaker. Want more random fun? Try LeetCode 478: Random Point in Circle or LeetCode 528: Random Pick with Weight. Ready to pin some points? Head to Solve LeetCode 497 on LeetCode and drop it today—your coding skills are pin-ready!