LeetCode 528: Random Pick with Weight
A clear explanation of weighted random sampling using prefix sums and binary search.
Tag
Randomized
15 notes
LeetCode 497: Random Point in Non-overlapping Rectangles
A clear explanation of uniformly picking an integer point from non-overlapping rectangles using prefix sums and binary search.
LeetCode 478: Generate Random Point in a Circle
A clear explanation of generating uniformly random points inside a circle using polar coordinates.
LeetCode 470: Implement Rand10() Using Rand7()
A clear explanation of generating a uniform random integer from 1 to 10 using only rand7 and rejection sampling.
LeetCode 398: Random Pick Index
A clear explanation of picking a uniformly random index for a target value using reservoir sampling, with an alternative hash map approach.
LeetCode 384: Shuffle an Array
A clear explanation of shuffling an array uniformly using the Fisher-Yates algorithm while supporting reset.
LeetCode 382: Linked List Random Node
A clear explanation of selecting a random linked list node with equal probability using reservoir sampling.
LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed
A clear explanation of designing a randomized multiset with average O(1) insert, remove, and getRandom operations.
LeetCode 380: Insert Delete GetRandom O(1)
A clear explanation of designing a randomized set with average O(1) insert, remove, and getRandom operations.
Array Shuffle
Generate a uniform random permutation of an array in-place.
Randomized Quicksort
Quicksort variant that selects pivots randomly to avoid worst case patterns.
Floyd Sampling
Select k distinct integers uniformly from a fixed range without shuffling the whole range.
Weighted Reservoir Sampling
Select a random sample from a stream where each item has a nonnegative weight.
Reservoir Sampling
Select a uniform random sample from a stream of unknown length using fixed memory.
Randomized Quickselect
Quickselect with random pivot selection to achieve robust expected linear time.