Abstract / Summary

Given a list of non overlapping rectangles pick a random point from one of them weighted by their area.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 40% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Math
• Ordered Set
• Prefix Sum
• Randomized
• Reservoir Sampling

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class builds a data structure that enables random selection of integer points from a collection of axis-aligned rectangles. During construction it computes a cumulative weight for each rectangle based on the count of lattice points it contains. The pick method then draws a uniform random integer within the total weight range, locates the corresponding rectangle, and finally returns a random point inside that rectangle.

Key Steps

The constructor receives a list of rectangles, each expressed as [x1, y1, x2, y2]. It stores the original list, prepares a mapping from cumulative weights to rectangle indices, and aggregates the total number of points.

def __init__(self, rects: List[List[int]]):
    self.rects  = rects
    self.points = {}
    self.total  = 0
    for i, r in enumerate(rects):
        area = (r[2] - r[0] + 1) * (r[3] - r[1] + 1)
        self.total += area
        self.points[self.total] = i

The area variable actually counts the integer lattice points inside the rectangle, because the coordinates are inclusive. By adding one to each dimension the calculation correctly includes the boundary points. The cumulative sum self.total grows monotonically, and each entry in self.points maps a threshold value to the index of the rectangle that contributes up to that threshold.

The pick method generates a random integer in the range [0, self.total-1]. It then iterates over the sorted threshold keys to find the first threshold that exceeds the random value, thereby identifying the rectangle that contains the selected point.

def pick(self) -> List[int]:
    i = randint(0, self.total - 1)
    r = None
    for p in sorted(self.points):
        if p > i:
            r = self.rects[self.points[p]]
            return [randint(r[0], r[2]), randint(r[1], r[3])]

Once the rectangle r is located, two independent calls to randint produce a random x-coordinate between r[0] and r[2] and a random y-coordinate between r[1] and r[3]. The method returns the point as a two-element list.

Edge Cases Handled

The area computation adds one to each side length, which correctly handles rectangles that degenerate to a single point (where x1 == x2 and y1 == y2). In such cases the product yields 1, ensuring that the rectangle contributes exactly one possible point to the overall distribution. The inclusive use of randint for both the cumulative selection and the coordinate generation guarantees that every lattice point inside every rectangle, including those on the edges, has a non-zero probability of being chosen.

If a rectangle has zero width or zero height (for example x1 > x2 or y1 > y2), the subtraction followed by +1 would produce a non-positive count, but the code assumes well-formed input where x1 ≤ x2 and y1 ≤ y2. Within the intended input domain the implementation correctly accounts for rectangles of minimal size and for those that span large coordinate ranges.

Performance Optimizations Observed

The cumulative weight approach eliminates the need to recompute the number of points in each rectangle on every call to pick. By storing the total count of points across all rectangles in self.total, the random selection step reduces to a single integer generation. The dictionary self.points provides O(1) access from a threshold value to the rectangle index once the appropriate threshold is identified.

Sorting the keys of self.points only once per call to pick ensures that the search proceeds in ascending order, which aligns with the monotonic nature of the cumulative thresholds. Although the current implementation uses a linear scan, the presence of the cumulative mapping itself is a key optimization that transforms the problem from a potentially expensive per-pick area calculation to a simple lookup based on pre-computed aggregates. The use of Python’s built-in randint for both the selection of the threshold and the generation of coordinates leverages highly optimized C-level random number generation, contributing to fast execution of the random sampling process.

Imagine you have several big rectangular boxes sitting in a room, and each box is filled with tiny, colorful toy blocks. This code is like a helper who knows exactly which boxes are in the room.

When the helper first starts, it looks at every box to see how much space is inside. It keeps track of all this space by adding it up as it goes along. It marks down the size of each box so it knows how many toy blocks can fit into each spot.

When it is time to pick a random toy block, the helper first picks a secret lucky number. This number helps the helper decide which box to look inside. It walks through a list of the boxes it made earlier, checking the sizes. Once the helper finds the right box for that lucky number, it reaches inside and grabs a block. To grab the block, it chooses a random spot from the bottom left corner to the top right corner of that box, making sure the block is found somewhere inside.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java		TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python				Java	Go
	LeetcodeHelp	C++	Python				Java
	Progiez	C++	Python				Java
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai						Java
	everthis			JS
	halfrost							Go
	haoel	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	ruoru					Rust
	suxrobGM				C#
	trung-hn		Python
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality