Pattern Guide
Randomized Algorithms
"Random choices eliminate worst cases. Reservoir sampling, random pivot, shuffle."
Randomized algorithms use randomness to avoid adversarial worst cases, simplify implementation, or achieve expected O(n log n) where deterministic fails. Key techniques: reservoir sampling (uniform random sample from stream), Fisher-Yates shuffle (perfect permutation), randomized QuickSelect (O(n) expected), random pivot QuickSort, and skip lists. Essential for streaming problems and when input might be adversarial.
Problems you can solve with this pattern
5 problems · click any to start solving
// Reservoir sampling — pick k items uniformly at random from stream
function reservoirSample(stream, k) {
const reservoir = stream.slice(0, k);
for (let i = k; i < stream.length; i++) {
const j = Math.floor(Math.random() * (i + 1)); // random in [0, i]
if (j < k) reservoir[j] = stream[i]; // replace with probability k/(i+1)
}
return reservoir;
}
// Fisher-Yates shuffle — O(n), uniform random permutation
function shuffle(arr) {
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}
// Randomized QuickSelect — O(n) expected k-th smallest
function quickSelect(arr, k) { // k is 1-indexed
const pivot = arr[Math.floor(Math.random() * arr.length)];
const lo = arr.filter(x => x < pivot);
const mid = arr.filter(x => x === pivot);
const hi = arr.filter(x => x > pivot);
if (k <= lo.length) return quickSelect(lo, k);
if (k <= lo.length + mid.length) return pivot;
return quickSelect(hi, k - lo.length - mid.length);
}Randomized algorithms exchange deterministic guarantees for expected-case guarantees. The classic example: QuickSort with fixed pivot is O(n²) on sorted input — with random pivot, expected O(n log n) regardless of input. Reservoir sampling solves "pick k uniform random items from a stream of unknown length" elegantly: keep k items, each new item i replaces a random previous item with probability k/i.
// Reservoir sampling — pick k items uniformly at random from stream
function reservoirSample(stream, k) {
const reservoir = stream.slice(0, k);
for (let i = k; i < stream.length; i++) {
const j = Math.floor(Math.random() * (i + 1)); // random in [0, i]
if (j < k) reservoir[j] = stream[i]; // replace with probability k/(i+1)
}
return reservoir;
}
// Fisher-Yates shuffle — O(n), uniform random permutation
function shuffle(arr) {
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}
// Randomized QuickSelect — O(n) expected k-th smallest
function quickSelect(arr, k) { // k is 1-indexed
const pivot = arr[Math.floor(Math.random() * arr.length)];
const lo = arr.filter(x => x < pivot);
const mid = arr.filter(x => x === pivot);
const hi = arr.filter(x => x > pivot);
if (k <= lo.length) return quickSelect(lo, k);
if (k <= lo.length + mid.length) return pivot;
return quickSelect(hi, k - lo.length - mid.length);
}When to randomize:
- QuickSort/QuickSelect on unknown input (avoid O(n²) worst case)
- Sampling from stream without knowing length
- Hashing (random hash functions avoid collisions)
- Testing / approximation algorithms
Fisher-Yates correctness: Each of n! permutations is equally likely. After k iterations, the last k elements form a uniform random k-permutation.