LeetCode 497: Random Point in Non-overlapping Rectangles Solution in Python – A Step-by-Step Guide
Imagine you’re a treasure hunter tasked with dropping a pin randomly across a map dotted with non-overlapping rectangular zones—like [[1,1,5,5]] (a 4x4 grid)—and you need to pick any point within these zones with equal chance, say [3, 4] or [2, 2]. With multiple rectangles, like [[1,1,5,5], [6,6,8,8]], you’d want every possible point to have the same odds. That’s the probabilistic adventure of LeetCode 497: Random Point in Non-overlapping Rectangles, a medium-level problem that’s a fun mix of randomness and geometry. Using Python, we’ll solve it two ways: the Best Solution, a prefix sum with binary search approach that’s fast and clever, and an Alternative Solution, a brute force area iteration that’s intuitive but less efficient. With examples, code breakdowns, and a friendly tone, this guide will help you drop that pin—whether you’re new to coding or sharpening your treasure-hunting skills. Let’s map it out and dive in!
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!