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?

Section link icon

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

Section link icon

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.

Alternative Solution: Brute Force Area Iteration

Section link icon

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

Section link icon
  • 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

Section link icon
  • 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

Section link icon
  • 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

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

Final Thoughts: Drop That Pin

Section link icon

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!