cf.completefrontend
ARRAYS & HASHING · ADVANCED

Reservoir sampling

Pick k items at random from a stream of unknown length, keeping only k items in memory, so every item has the same chance of being picked.

Time O(n)Space O(k)3 practice problemsStep-through picture

The idea

Sometimes items arrive one at a time and you don't know how many will come, like log lines or user events. You want a fair random sample of k of them, but you can't store them all and pick later.

Reservoir sampling keeps a reservoir of k items. The first k items go straight in. After that, when the item number seen arrives, pick a random whole number j from 0 to seen - 1. If j is less than k, the new item replaces reservoir[j]; otherwise it's skipped.

This gives each new item a k / seen chance to get in, and it works out so that, at every moment, each item seen so far has exactly a k / seen chance of being in the reservoir.

An everyday example

A photo wall with room for five pictures

Your fridge has room for 5 photos, and friends keep sending photos all year. You want the fridge to show a fair random 5 of all the photos you ever got. The first 5 go up. When photo number 20 arrives, you give it a 5 in 20 chance to go up; if it wins, it replaces one of the 5 on the fridge, chosen at random. Older photos slowly get fewer chances to stay, but new ones also get fewer chances to get in, and the two balance out.

How the example maps to the code
In the exampleIn the code
The fridge with 5 spotsreservoir, of size k
How many photos you've receivedseen
Rolling to decide if the new photo goes upj = Math.floor(random() * seen)
The new photo wins and replaces spot jif (j < k) reservoir[j] = item

From the slow way to reservoir sampling

  1. The obvious way to pick k random items from a stream is to store the whole stream, then shuffle it and take the first k. That needs memory for every item, which fails when the stream is a log with billions of lines or never ends.
  2. Start with k = 1. Keep the first item. When the second arrives, keep it instead with chance 1 in 2. When the third arrives, take it with chance 1 in 3. After three items, each has the same 1 in 3 chance, and that pattern continues for any length.
  3. For k slots, the item number seen should get in with chance k / seen, and when it does, push out one of the k kept items at random. A single random whole number j from 0 to seen - 1 decides both: j < k has exactly that chance, and when it's true, j is an evenly chosen slot.
  4. The first k items go straight in, since each must be kept with chance k / k = 1. One counter, one random number per later item, and k slots of memory: that loop is reservoir sampling.

How it works

  1. Create an empty reservoir and set seen = 0.
  2. For each item in the stream, add 1 to seen.
  3. While the reservoir has fewer than k items, push the item in.
  4. Otherwise pick j = Math.floor(random() * seen), a whole number from 0 to seen - 1.
  5. If j < k, replace reservoir[j] with the item. Otherwise skip it.
  6. When the stream ends, return reservoir.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function reservoirSample(stream, k, random = Math.random) {
  2. const reservoir = [];
  3. let seen = 0;
  4. for (const item of stream) {
  5. seen++;
  6. if (reservoir.length < k) {
  7. reservoir.push(item);
  8. } else {
  9. const j = Math.floor(random() * seen);
  10. if (j < k) {
  11. reservoir[j] = item;
  12. }
  13. }
  14. }
  15. return reservoir;
  16. }

How fast it is

TimeO(n)
Extra memoryO(k)

Each of the n items takes one random number and maybe one write. The reservoir never holds more than k items.

  • Best caseO(n)

    Every item is read once. A stream shorter than k only pushes, with no random numbers at all.

  • Average caseO(n)

    One counter update and at most one random number and one write per item.

  • Worst caseO(n)

    No stream is slower per item. Long streams just take proportionally longer, since every item must be read.

Common mistakes

  • Using Math.floor(random() * k) to choose whether to replace, which gives every new item the same chance and favors late items.
  • Counting seen from 0 for the current item, which makes j range one too small and biases the sample.
  • Storing the whole stream and shuffling it, which defeats the purpose when the stream is huge.
  • Expecting the reservoir to keep the stream's order. Replacements land in random spots.

When to use it

Look for these clues in a problem:

  • Items arrive as a stream, and you don't know how many there will be.
  • You must pick one or k items uniformly at random.
  • You can't store the whole stream, or you can read it only once.
  • Tests give you the random numbers to use, so the result is repeatable.

Check yourself

Answer each one in your head first, then open it.

In the trace, why is m6 skipped when j is 3?

An item gets in only when j < k, and k is 3, so only j values 0, 1, and 2 let it in.

What chance does m1 have of being in the final sample of 7 with k = 3?

3 in 7, the same as every other line. It starts certain, then survives each of steps 4 to 7 with chances 3/4, 4/5, 5/6, and 6/7, which multiply to 3/7.

How can one random number decide both whether and where the new item goes?

j is spread evenly over 0 to seen - 1. The chance that j < k is k / seen, and when it is, each slot from 0 to k - 1 is equally likely.

How much memory does sampling 100 lines from a billion-line log take?

100 lines plus one counter. The memory doesn't depend on the log's length.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule to keep: once seen items have arrived, with seen >= k, each of them is in the reservoir with chance k / seen. After the first k items, every one of them is in for sure, and k / k = 1, so the rule starts out true.

Now item number t arrives. It gets in with chance k / t, which fits the rule. An item already in the reservoir is pushed out only if the new item gets in (chance k / t) and lands on its slot (chance 1 / k), so it survives with chance 1 - 1 / t = (t - 1) / t. It was in with chance k / (t - 1), so now it's in with chance k / (t - 1) × (t - 1) / t = k / t. The rule holds after every item.

The loop ends when the stream does, and the rule then says every item had the same chance, k / n. If the stream had fewer than k items, they were all pushed in and all kept, which is the only fair answer. And because the rule holds after every item, you can stop reading at any moment and still have a fair sample of what came so far.

Going deeper

4 more ideas

Why every item has the same chance

Item number seen gets in with chance k / seen. An item already in the reservoir is knocked out at a later step t only if the new item gets in (chance k / t) and lands on its spot (chance 1 / k), so it survives that step with chance 1 - 1 / t = (t - 1) / t. Multiplying these from its arrival to item n, the fractions cancel and leave k / n, the same for every item.

Picking just one item

With k = 1, the rule becomes: replace the kept item with item number seen when Math.floor(random() * seen) is 0, a chance of 1 / seen. The first item is always kept at first, the second replaces it half the time, the third a third of the time, and so on.

Weighted sampling

If items have weights and heavier items should be more likely, one known method gives each item the key random() ** (1 / weight) and keeps the k items with the largest keys, using a min-heap of size k. With every weight equal to 1, this is just keeping the k largest random numbers, another way to sample fairly.

Cost

Each item takes O(1) time, so a stream of n items takes O(n) time. Only k items are ever stored: O(k) space, however long the stream is.

Work it by hand

Every step in a table, with why

Keep a random sample of 3 from a stream of 7 log lines, using four given random numbers.

stream = ["m1", "m2", "m3", "m4", "m5", "m6", "m7"], k = 3, random numbers 0.25, 0.8, 0.5, 0.1

StepitemseenDrawjreservoir afterWhy
1m11--[m1]The reservoir has room, so m1 goes straight in. No random number is used.
2m22--[m1, m2]Still room: reservoir.length is 1, less than k = 3.
3m33--[m1, m2, m3]The reservoir is full now. From here on, every item needs a draw.
4m44floor(0.25 * 4)1[m1, m4, m3]j can be 0 to 3, and 1 < 3, so m4 gets in and replaces m2 in slot 1. Its chance was 3 in 4.
5m55floor(0.8 * 5)4[m1, m4, m3]4 is not less than 3, so m5 is skipped. The reservoir doesn't change.
6m66floor(0.5 * 6)3[m1, m4, m3]3 is not less than k = 3, so m6 is skipped too. Only j values 0, 1, and 2 let an item in.
7m77floor(0.1 * 7)0[m7, m4, m3]0 < 3, so m7 replaces m1 in slot 0. The stream ends here.

The sample is [m7, m4, m3]. Only 3 items were ever stored, and over all possible random numbers each of the 7 lines ends up in the sample with the same chance, 3 in 7.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Reservoir samplingO(n)O(k)The stream's length is unknown or it's too big to store, and you need a fair sample in one pass.
Store everything, then shuffleO(n)O(n)The data fits in memory and you may need several samples from it.
Random keys with a heapO(n log k)O(k)You need to merge samples from several machines, or the items have weights.
Pick k random indexesO(k)O(k)The length is known and items can be read by index, like an array.

Extra memory: O(k): the reservoir never holds more than k items, plus the counter seen, however long the stream is.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Reservoir sampling and the other approaches, on a scale where each line up is 10 times more steps.
  • Reservoir sampling, Store everything, then shuffle, Pick k random indexes O(n)
  • Random keys with a heap O(n log k)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Reservoir sampling101,0001 million
Store everything, then shuffle101,0001 million
Random keys with a heap339,96620 million
Pick k random indexes101,0001 million

Inputs that need care

5 tricky inputs
A stream shorter than k: two items with k = 4
Both are pushed and the function returns them, fewer than k items. Callers must not assume the result has length k.
k = 0
reservoir.length < 0 is never true, and j < 0 never is either, so it returns []. It still draws a random number for every item, so return early when k is 0.
k = 1
It keeps one item. The item number seen takes over when j is 0, a chance of 1 in seen.
Repeated values in the stream: ["a", "a", "b"]
Each arrival is its own item, so "a" is twice as likely to appear in the sample as "b". Remove repeats first if each distinct value should have the same chance.
You need the sample in stream order
Replacements land in random slots, so the reservoir's order is mixed. Store [seen, item] pairs and sort by seen at the end.

Variations and follow-ups

Twists interviewers add

Skipping ahead

When seen is large, most items are skipped, yet each still costs a random number. A known improvement draws how many items to skip before the next replacement, so it needs only about k × log(n / k) random numbers.

Random keys, keep the smallest

Give each item a random number and keep the k items with the smallest numbers, using a max-heap of size k. It's also fair, and samples from separate streams can be merged by keeping the k smallest numbers overall.

Known length

If the length n is known in advance and items can be accessed by index, run k steps of the Fisher-Yates shuffle, or pick k distinct random indexes. That reads only the chosen items.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "stream", "unknown length", "can't store everything", "random line from a huge file", or "each item equally likely".
  • Explain the chance: "item number seen gets in with chance k / seen, and an item already in survives each later step with chance (t - 1) / t, so everything comes out as k / n."
  • Test with a fixed list of random numbers, as in the trace, so the expected reservoir is known. Include a stream shorter than k.
  • The usual follow-up is "prove it's fair". Walk through the survival product. Another is "what if items have weights?": give each item the key random() ** (1 / weight) and keep the k largest keys in a min-heap.

Where frontend code uses it

The same idea in real UI code
  • Client-side telemetry can keep a fixed-size random sample of errors or performance entries during a long session, then send only those.
  • Showing a random "featured" item from a feed that's streamed in pages, without loading every page first.
  • Sampling events in a Web Worker that processes a long log file read in chunks.

Related algorithms