Abstract / Summary

Pick an element randomly based on given weights so each element's chance matches its weight proportion.

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 49% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Math
• Prefix Sum
• Randomized

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 presented class implements a weighted random selection mechanism. During construction it builds a prefix-sum array from the supplied weight vector. The pickIndex method draws a random integer in the range [1, totalWeight] and uses binary search to locate the first prefix sum that meets or exceeds the drawn value. The index of that prefix sum is returned, giving each element a selection probability proportional to its weight.

Construction of the Prefix-Sum Array

Solution(vector<int>& w) {
    sum.reserve(w.size());

    int64_t total = 0;
    for (auto x : w)
    {
        total += x;
        sum.push_back(total);
    }
}

The constructor receives a vector of integer weights. It first reserves space in the internal sum vector equal to the number of weights, preventing repeated reallocations as the prefix sums are appended. An int64_t accumulator named total aggregates the running sum. For each weight x the accumulator is increased and the new total is stored in sum. The resulting sum vector holds cumulative totals, where sum[i] equals the sum of the first i+1 weights. This structure enables O(log n) lookup later.

Edge Cases Addressed

When the input contains a single weight, the loop runs once, sum ends with a single element equal to that weight, and pickIndex will always return index 0, correctly reflecting a 100 % selection chance. The use of a 64-bit accumulator safeguards against overflow when the sum of many 32-bit weights exceeds the range of int. The reserve call also gracefully handles the case where the weight vector is empty; the subsequent loop simply does not execute, leaving sum empty. (The later pickIndex call would then operate on an empty sum, which is outside the intended usage scenario.)

Random Number Generation

int maxx = sum.back();

std::random_device r;
std::default_random_engine engine(r());
std::uniform_int_distribution<int> uniform_dist(1, maxx);
int x = uniform_dist(engine);

maxx captures the total weight, the last element of the prefix-sum array. A random_device supplies entropy to seed a default_random_engine. The engine is constructed anew on each invocation of pickIndex, ensuring that the sequence of generated numbers does not depend on previous calls. The uniform integer distribution is configured with inclusive bounds [1, maxx], guaranteeing that every integer within the total weight range has an equal chance of being drawn.

Edge Cases Addressed

If the total weight is exactly 1, the distribution range collapses to a single value, and the generated x will always be 1. The binary search that follows will therefore always locate the first prefix sum that is at least 1, which is the correct behavior for a single-unit weight scenario. The use of int for maxx and the distribution is safe because maxx originates from a 64-bit sum but is cast to int; this implicitly assumes that the total weight fits within the 32-bit signed integer range, which aligns with typical problem constraints.

Binary Search for the Target Index

auto p = lower_bound(sum.begin(), sum.end(), x);
return distance(sum.begin(), p);

std::lower_bound performs a binary search over the sorted prefix-sum vector to find the first element that is not less than the random value x. Because the prefix sums are monotonically increasing, the position returned corresponds to the weight bucket that contains x. The distance from the beginning of the vector to this iterator yields the zero-based index to be returned.

Edge Cases Addressed

When x equals a prefix sum exactly, lower_bound returns an iterator to that element, ensuring that the corresponding index is selected. If x is larger than all but the last prefix sum, the iterator points to the final element, correctly mapping the random draw to the last weight bucket. The algorithm also works when multiple weights share the same value, as the cumulative nature of the prefix sums preserves the correct boundaries.

Performance Optimizations

The constructor’s reserve call eliminates the need for dynamic resizing during the accumulation loop, reducing allocation overhead and improving cache locality. Storing cumulative totals in a contiguous vector<int64_t> enables the binary search to operate on a compact memory layout, which benefits branch prediction and prefetching. The use of std::lower_bound leverages a highly tuned implementation of binary search, providing logarithmic lookup time without manual loop management. By constructing the random engine locally for each call, the code avoids shared mutable state, which can be a source of contention in multithreaded contexts.

The combination of these choices results in a solution that builds its internal data structure in linear time relative to the number of weights and answers each selection request in logarithmic time, while keeping memory usage proportional to the input size. The reliance on standard library components ensures that the implementation benefits from compiler optimizations and platform-specific enhancements.

Imagine a row of treasure chests. Some chests are very big, and some are tiny. The big chests have more chances to be picked, just like a game where the biggest pile of toys gets chosen most often.

The first part of the code goes through all the chests one by one. It keeps a running total of how much space they take up. Think of it like walking along a line and marking the distance as you pass each chest. The tiny chests give you a tiny step, while the big chests give you a giant step. By the end, you have a long ruler that shows exactly where each chest starts and ends.

When it is time to pick a chest, the code uses a magical spinning wheel to pick a random number. This number is used to find the right spot on that long ruler. Because the big chests cover a much larger part of the ruler than the tiny ones, the random number is much more likely to land in a space belonging to a big chest.

After picking the spot, the code looks at the ruler to see which chest holds that spot. It quickly checks the marks made earlier to decide which chest was chosen. This makes sure that the bigger the chest, the more often it gets picked, making it a very fair way to play the game.

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	JS	Java		Rust	Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

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