Skip to content

Reservoir Sampling Problems

4 Reservoir Sampling LeetCode problems · Browse tasks by difficulty and choose your next practice problem.

Learn the coding interview patterns behind these problems.

Sample a stream without knowing its length

Reservoir sampling keeps a uniform sample while processing items one at a time. For one sample, keep the first item and replace it with the i-th item with probability 1/i. This is useful for a linked list that cannot be indexed directly or for matching positions discovered during a scan.

When to use it

Use a reservoir when the stream length is unknown or storing every candidate is undesirable. In Random Pick Index, only occurrences of the requested value count as candidates. Weighted choices, such as rectangles with different numbers of integer points, require a different weighting argument.

Worked example

The stream arrives as A, then B, then C. Keep one item.

  1. Keep A initially. When B arrives, replace the current item with probability 1/2.
  2. When C arrives, replace the current item with probability 1/3.
  3. A survives with probability (1/2) × (2/3) = 1/3; B has the same probability. C is chosen with probability 1/3.

Each of A, B, and C is selected with probability 1/3, using only one stored candidate.

Time and space

Sampling one item from n candidates takes O(n) time and O(1) auxiliary space. A reservoir of k items uses O(k) space; after the first k items, accept item i with probability k/i and replace a uniformly chosen reservoir position.

Mistakes to check

  • Draw an unbiased integer in the intended range. Reducing an arbitrary random integer with modulo can introduce bias.
  • For a filtered stream, increment the candidate count only when the item qualifies. Counting non-matching values changes the probabilities.
  • Repeated requests may each require another scan. If the data is fixed and requests are frequent, storing candidate indices can be a better time-space tradeoff.

Further reading: Jeffrey Vitter: Random Sampling with a Reservoir

Guide reviewed .

All Reservoir Sampling problems