Reservoir Sampling & Randomized Pick
Build a class, Solution, around a singly linked list, that hands back the value of a node picked at random.
Solution(ListNode head)receives the first node of the list.int getRandom()returns the value of one node of the list, chosen so that every node has the same chance. Each call makes a new, independent choice.
Nodes may hold equal values, so a value stored in two nodes comes back twice as often as a value stored in one. Any value that is in the list is a correct single answer; long runs of calls are checked for an even spread over the nodes. LeetCode's follow-up asks what to do when the list is too long to store and its length is unknown, and whether you can pick with no extra space.
1 -> 2 -> 3. Each getRandom() returns 1, 2 or 3, each with chance 1/3, so many other outputs are just as correct; LeetCode shows one possible run.Reservoir Sampling
stream of items ➔ keep each with chance 1/i ➔ one uniform random item| 1 | import random |
| 2 | from typing import Optional |
| 3 | |
| 4 | |
| 5 | class ListNode: |
| 6 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 7 | self.val = val |
| 8 | self.next = next |
| 9 | |
| 10 | |
| 11 | class Solution: |
| 12 | """Linked List Random Node: reservoir sampling, one pass per pick and O(1) extra space. |
| 13 | Time: O(N) per getRandom | Space: O(1) |
| 14 | """ |
| 15 | |
| 16 | def __init__(self, head: Optional[ListNode]): |
| 17 | self.head = head # Keep only the head: every pick walks the list again |
| 18 | |
| 19 | def getRandom(self) -> int: |
| 20 | result, i = 0, 0 # result: the current pick; i: nodes seen so far |
| 21 | node = self.head |
| 22 | while node: |
| 23 | # 1. Count This Node: |
| 24 | # i must count node before the draw, so the first node is always taken (randrange(1) is 0). |
| 25 | i += 1 |
| 26 | |
| 27 | # 2. Draw With Chance 1/i: |
| 28 | # randrange(i) is one of 0..i - 1, so it lands on 0 with chance exactly 1/i; every earlier |
| 29 | # node then keeps its own share, since it survives this draw with chance (i - 1)/i. |
| 30 | if random.randrange(i) == 0: |
| 31 | result = node.val |
| 32 | |
| 33 | # 3. Move to the Next Node: |
| 34 | # The same draw repeats at every node until the whole list has been walked once. |
| 35 | node = node.next |
| 36 | # 4. Return the Last Survivor: |
| 37 | # After the last node every node has had chance exactly 1/n, with no copy of the list ever made. |
| 38 | return result |
i nodes, each of them is result with chance exactly 1/i.Reservoir sampling picks a uniform random node in one pass without knowing the length: walk the list, count the nodes with i, and let the i-th node replace result with chance exactly 1/i, drawn as random.randrange(i) == 0. It is fair because the shares stay equal at every step: the new node gets in with 1/i, and each earlier node, which was result with chance 1/(i - 1), survives the draw with (i - 1)/i, which leaves it at 1/i too; after the last node every node has chance 1/n, with no copy of the list. The trap is the chance: i must count the current node before the draw, so the first node is always taken (randrange(1) is 0). randrange(i + 1), a chance of 1/(i + 1), keeps the head only half the time and can leave result at its starting 0, and returning at the first successful draw always returns the head.
See it run
Reservoir sampling over [10, 20, 30, 40] with one fixed run of draws
i 0draw -result 0
The top row is the list, the middle row is the draw made at each node, and the bottom row shows which node is result.
nodethe node being countedhitthe draw was 0, so this node replaces resultmissthe draw was not 0, so result staysresultthe node that is result now
The list is [10, 20, 30, 40]. result starts at 0 and i starts at 0. This run uses the draws shown in the middle row.
Gotcha 1 of 3
- The trap
Gotcha 1: Drawing
randrange(i + 1)instead ofrandrange(i)Mistakeif random.randrange(i + 1) == 0:Fixif random.randrange(i) == 0:What happens:
i += 1already counts the current node, so nodeimust win with chance 1/i. The head then wins with chance 1/1, so it is always kept first. Withrandrange(i + 1), the head wins only half the time. For the list [1, 2], each of 0, 1 and 2 is returned in one third of the calls. The 0 isresult's starting value, which is not in the list.Example: head = [1, 2], the set of values from 100 callsMistake: returns [0, 1, 2]Fix: returns [1, 2]
- Switch to Insert Delete GetRandom when the set of items changes between picks, as in Insert Delete GetRandom
O(1)(LC 380): values are inserted and removed, and each pick must beO(1), not one pass over a fixed sequence. See Insert Delete GetRandom - Switch to Lower Bound when the chances are unequal and every weight is known up front, as in Random Pick with Weight (LC 528): an item must come back in proportion to its weight, so a one-pass draw that gives every element the same 1/i chance is the wrong tool. See Lower Bound
Deep Dive
Why every node ends with chance 1/n
Look at node j in a list of n nodes. It becomes result with chance 1/j at its own step. Then every later node i must fail to replace it. Node i replaces result with chance 1/i, so node j survives that step with chance (i - 1)/i.
The chance that node j is the final result is the product: 1/j * j/(j + 1) * (j + 1)/(j + 2) * ... * (n - 1)/n. Each numerator cancels the denominator before it. What remains is 1/n. This is the card's invariant, applied at the last node.
The picture shows one run on the list [10, 20, 30, 40] with the draws 0, 1, 0, 2. Node 10 is taken at once. Node 20 misses. Node 30 hits, so result becomes 30. Node 40 misses, so the run returns 30.
Checking the claim by counting every possible run
At the i-th node, random.randrange(i) has i equally likely values. For four nodes, a run is one choice from 1 * 2 * 3 * 4 = 24 possible draw sequences, and each sequence has the same chance.
Count the final result over all 24 sequences. Each of the values 10, 20, 30 and 40 is returned in exactly 6 sequences. That is 6/24 = 1/4 for each node, as the proof says.
Now use randrange(i + 1), the trap. There are 2 * 3 * 4 * 5 = 120 sequences. The values 10, 20, 30, 40 and the starting value 0 are each returned 24 times. So the head is no longer always taken at its step, and result can stay at 0, a value that is not in the list.
What i must count
i is the number of nodes seen so far, including the current one. The increment i += 1 comes before the draw. At the first node, randrange(1) can only return 0, so the first node is always taken. This gives result a real value from the list.
In Random Pick Index (LC 398), the nodes are the positions of nums where nums[index] == target. i must count only those positions. For nums = [1, 2, 3, 3, 3] and target = 3, there are three matches, at indexes 2, 3 and 4. The draws are randrange(1), randrange(2) and randrange(3). Over all 6 sequences, each of the three indexes is returned twice.
If i counted every position of nums, the chances would not be equal. A matching position would enter with chance 1/(its position + 1), not 1/(matches so far).
The cost, and when this card is the wrong tool
getRandom walks the list once, and each node costs one draw. The time is O(N) per call. The space is O(1), because result, i and node are the only variables. The class stores only head.
A different method copies the values into an array in __init__, and getRandom returns random.choice(values). Each call takes O(1) time, but the array needs O(N) space. Choose by the constraints: reservoir sampling for a stream or a list that is too large to copy, and the array when there are many calls.
If the items change between picks, as in Insert Delete GetRandom O(1) (LC 380), keep the items in an array. If the chances are unequal, as in Random Pick with Weight (LC 528), a one-pass draw with equal chances is the wrong tool.
60-Second Pitch
"I need one uniform pick from a list that I can read only once, with no copy. I walk the list and count the nodes with i. At the i-th node, I replace result with chance 1/i, using random.randrange(i) == 0. The new node gets 1/i. Each earlier node was result with chance 1/(i - 1) and survives with (i - 1)/i, so it also has 1/i. After the last node, every node has chance 1/n. The cost is O(N) time per call and O(1) space. If there are many calls and memory is not a problem, I would copy the values into an array and use random.choice."
Common Questions
- Why is the chance of each node exactly 1/n?
Node
jis taken with chance 1/j. It then survives each later nodeiwith chance (i - 1)/i. The product is 1/j * j/(j + 1) * ... * (n - 1)/n. The terms cancel in pairs, and 1/n remains.- What are the time and space of
getRandom? O(N)time per call, because it walks the whole list, andO(1)space. The class keeps onlyhead. A method that copies the list into an array usesO(N)space and picks inO(1)time.- What changes for Random Pick Index (LC 398)?
Walk
numsand only count the positions wherenums[index] == target. Leticount these matches. Whenrandom.randrange(i) == 0, setresult = index. Every matching index then has chance 1/(number of matches).- How would you pick
kitems, not one? Keep a list of
kitems. Put the firstkitems in it. For each later itemi, drawj = random.randrange(i). Ifj < k, replace the item at positionjwith the new item. Every item then has chance k/n. For 5 items and k = 2, all 10 possible pairs are equally likely.- When would you not use reservoir sampling?
SWE Reasoning
Spot it
- The task is a uniform random pick from a list or a stream, and every element must have the same chance.
- The data is read once, in order, and its length is not known at the start. This is common for a linked list or a stream.
- Memory is limited, so you cannot copy the elements into an array.
- Only some elements qualify, as in Random Pick Index (LC 398), where only the indexes of
targetcount. - The set of items does not change between picks, and the chances are equal.
The invariant, step by step
result = 0andi = 0at the start.nodepoints to the head.- At each node,
i += 1counts the node first. Soiis the number of nodes seen, including this one. random.randrange(i)returns one of0toi - 1. It returns 0 with chance exactly 1/i, and thenresult = node.val.- Before this node, each earlier node was
resultwith chance 1/(i - 1). It staysresultonly when the draw is not 0, which has chance (i - 1)/i. So it keeps 1/(i - 1) * (i - 1)/i = 1/i. - The new node has chance 1/i too. So after
inodes, each of them isresultwith chance 1/i. - After the last node, every node has chance 1/n. The function returns
resultwithout a copy of the list.
Traps
randrange(i + 1)instead ofrandrange(i). The head is taken only half the time. For the list[1, 2], the values 0, 1 and 2 are each returned in one third of the calls, and 0 is not in the list.- Return at the first hit.
randrange(1)is always 0, so the first node always hits. The function returns the head on every call. The loop must continue to the end. - Choose once in
__init__. Every call togetRandomthen returns the same value. Each call needs a new walk and new draws. icounts the wrong things. In Random Pick Index (LC 398),icounts matches, not positions. Otherwise the chances are not equal.iis incremented after the draw. The draw would then use the count before the current node, and at the first noderandrange(0)raisesValueError.
Practice
Reservoir Sampling & Randomized Pick
Build a class, Solution, around a singly linked list, that hands back the value of a node picked at random.
Solution(ListNode head)receives the first node of the list.int getRandom()returns the value of one node of the list, chosen so that every node has the same chance. Each call makes a new, independent choice.
Nodes may hold equal values, so a value stored in two nodes comes back twice as often as a value stored in one. Any value that is in the list is a correct single answer; long runs of calls are checked for an even spread over the nodes. LeetCode's follow-up asks what to do when the list is too long to store and its length is unknown, and whether you can pick with no extra space.
1 -> 2 -> 3. Each getRandom() returns 1, 2 or 3, each with chance 1/3, so many other outputs are just as correct; LeetCode shows one possible run.Reservoir Sampling
stream of items ➔ keep each with chance 1/i ➔ one uniform random item| 1 | import random |
| 2 | from typing import Optional |
| 3 | |
| 4 | |
| 5 | class ListNode: |
| 6 | def __init__(self, val: int = 0, next: Optional["ListNode"] = None): |
| 7 | self.val = val |
| 8 | self.next = next |
| 9 | |
| 10 | |
| 11 | class Solution: |
| 12 | """Linked List Random Node: reservoir sampling, one pass per pick and O(1) extra space. |
| 13 | Time: O(N) per getRandom | Space: O(1) |
| 14 | """ |
| 15 | |
| 16 | def __init__(self, head: Optional[ListNode]): |
| 17 | self.head = head # Keep only the head: every pick walks the list again |
| 18 | |
| 19 | def getRandom(self) -> int: |
| 20 | result, i = 0, 0 # result: the current pick; i: nodes seen so far |
| 21 | node = self.head |
| 22 | while node: |
| 23 | # 1. Count This Node: |
| 24 | # i must count node before the draw, so the first node is always taken (randrange(1) is 0). |
| 25 | i += 1 |
| 26 | |
| 27 | # 2. Draw With Chance 1/i: |
| 28 | # randrange(i) is one of 0..i - 1, so it lands on 0 with chance exactly 1/i; every earlier |
| 29 | # node then keeps its own share, since it survives this draw with chance (i - 1)/i. |
| 30 | if random.randrange(i) == 0: |
| 31 | result = node.val |
| 32 | |
| 33 | # 3. Move to the Next Node: |
| 34 | # The same draw repeats at every node until the whole list has been walked once. |
| 35 | node = node.next |
| 36 | # 4. Return the Last Survivor: |
| 37 | # After the last node every node has had chance exactly 1/n, with no copy of the list ever made. |
| 38 | return result |
i nodes, each of them is result with chance exactly 1/i.Reservoir sampling picks a uniform random node in one pass without knowing the length: walk the list, count the nodes with i, and let the i-th node replace result with chance exactly 1/i, drawn as random.randrange(i) == 0. It is fair because the shares stay equal at every step: the new node gets in with 1/i, and each earlier node, which was result with chance 1/(i - 1), survives the draw with (i - 1)/i, which leaves it at 1/i too; after the last node every node has chance 1/n, with no copy of the list. The trap is the chance: i must count the current node before the draw, so the first node is always taken (randrange(1) is 0). randrange(i + 1), a chance of 1/(i + 1), keeps the head only half the time and can leave result at its starting 0, and returning at the first successful draw always returns the head.
See it run
Reservoir sampling over [10, 20, 30, 40] with one fixed run of draws
i 0draw -result 0
The top row is the list, the middle row is the draw made at each node, and the bottom row shows which node is result.
nodethe node being countedhitthe draw was 0, so this node replaces resultmissthe draw was not 0, so result staysresultthe node that is result now
The list is [10, 20, 30, 40]. result starts at 0 and i starts at 0. This run uses the draws shown in the middle row.
Gotcha 1 of 3
- The trap
Gotcha 1: Drawing
randrange(i + 1)instead ofrandrange(i)Mistakeif random.randrange(i + 1) == 0:Fixif random.randrange(i) == 0:What happens:
i += 1already counts the current node, so nodeimust win with chance 1/i. The head then wins with chance 1/1, so it is always kept first. Withrandrange(i + 1), the head wins only half the time. For the list [1, 2], each of 0, 1 and 2 is returned in one third of the calls. The 0 isresult's starting value, which is not in the list.Example: head = [1, 2], the set of values from 100 callsMistake: returns [0, 1, 2]Fix: returns [1, 2]
- Switch to Insert Delete GetRandom when the set of items changes between picks, as in Insert Delete GetRandom
O(1)(LC 380): values are inserted and removed, and each pick must beO(1), not one pass over a fixed sequence. See Insert Delete GetRandom - Switch to Lower Bound when the chances are unequal and every weight is known up front, as in Random Pick with Weight (LC 528): an item must come back in proportion to its weight, so a one-pass draw that gives every element the same 1/i chance is the wrong tool. See Lower Bound
Deep Dive
Why every node ends with chance 1/n
Look at node j in a list of n nodes. It becomes result with chance 1/j at its own step. Then every later node i must fail to replace it. Node i replaces result with chance 1/i, so node j survives that step with chance (i - 1)/i.
The chance that node j is the final result is the product: 1/j * j/(j + 1) * (j + 1)/(j + 2) * ... * (n - 1)/n. Each numerator cancels the denominator before it. What remains is 1/n. This is the card's invariant, applied at the last node.
The picture shows one run on the list [10, 20, 30, 40] with the draws 0, 1, 0, 2. Node 10 is taken at once. Node 20 misses. Node 30 hits, so result becomes 30. Node 40 misses, so the run returns 30.
Checking the claim by counting every possible run
At the i-th node, random.randrange(i) has i equally likely values. For four nodes, a run is one choice from 1 * 2 * 3 * 4 = 24 possible draw sequences, and each sequence has the same chance.
Count the final result over all 24 sequences. Each of the values 10, 20, 30 and 40 is returned in exactly 6 sequences. That is 6/24 = 1/4 for each node, as the proof says.
Now use randrange(i + 1), the trap. There are 2 * 3 * 4 * 5 = 120 sequences. The values 10, 20, 30, 40 and the starting value 0 are each returned 24 times. So the head is no longer always taken at its step, and result can stay at 0, a value that is not in the list.
What i must count
i is the number of nodes seen so far, including the current one. The increment i += 1 comes before the draw. At the first node, randrange(1) can only return 0, so the first node is always taken. This gives result a real value from the list.
In Random Pick Index (LC 398), the nodes are the positions of nums where nums[index] == target. i must count only those positions. For nums = [1, 2, 3, 3, 3] and target = 3, there are three matches, at indexes 2, 3 and 4. The draws are randrange(1), randrange(2) and randrange(3). Over all 6 sequences, each of the three indexes is returned twice.
If i counted every position of nums, the chances would not be equal. A matching position would enter with chance 1/(its position + 1), not 1/(matches so far).
The cost, and when this card is the wrong tool
getRandom walks the list once, and each node costs one draw. The time is O(N) per call. The space is O(1), because result, i and node are the only variables. The class stores only head.
A different method copies the values into an array in __init__, and getRandom returns random.choice(values). Each call takes O(1) time, but the array needs O(N) space. Choose by the constraints: reservoir sampling for a stream or a list that is too large to copy, and the array when there are many calls.
If the items change between picks, as in Insert Delete GetRandom O(1) (LC 380), keep the items in an array. If the chances are unequal, as in Random Pick with Weight (LC 528), a one-pass draw with equal chances is the wrong tool.
60-Second Pitch
"I need one uniform pick from a list that I can read only once, with no copy. I walk the list and count the nodes with i. At the i-th node, I replace result with chance 1/i, using random.randrange(i) == 0. The new node gets 1/i. Each earlier node was result with chance 1/(i - 1) and survives with (i - 1)/i, so it also has 1/i. After the last node, every node has chance 1/n. The cost is O(N) time per call and O(1) space. If there are many calls and memory is not a problem, I would copy the values into an array and use random.choice."
Common Questions
- Why is the chance of each node exactly 1/n?
Node
jis taken with chance 1/j. It then survives each later nodeiwith chance (i - 1)/i. The product is 1/j * j/(j + 1) * ... * (n - 1)/n. The terms cancel in pairs, and 1/n remains.- What are the time and space of
getRandom? O(N)time per call, because it walks the whole list, andO(1)space. The class keeps onlyhead. A method that copies the list into an array usesO(N)space and picks inO(1)time.- What changes for Random Pick Index (LC 398)?
Walk
numsand only count the positions wherenums[index] == target. Leticount these matches. Whenrandom.randrange(i) == 0, setresult = index. Every matching index then has chance 1/(number of matches).- How would you pick
kitems, not one? Keep a list of
kitems. Put the firstkitems in it. For each later itemi, drawj = random.randrange(i). Ifj < k, replace the item at positionjwith the new item. Every item then has chance k/n. For 5 items and k = 2, all 10 possible pairs are equally likely.- When would you not use reservoir sampling?
SWE Reasoning
Spot it
- The task is a uniform random pick from a list or a stream, and every element must have the same chance.
- The data is read once, in order, and its length is not known at the start. This is common for a linked list or a stream.
- Memory is limited, so you cannot copy the elements into an array.
- Only some elements qualify, as in Random Pick Index (LC 398), where only the indexes of
targetcount. - The set of items does not change between picks, and the chances are equal.
The invariant, step by step
result = 0andi = 0at the start.nodepoints to the head.- At each node,
i += 1counts the node first. Soiis the number of nodes seen, including this one. random.randrange(i)returns one of0toi - 1. It returns 0 with chance exactly 1/i, and thenresult = node.val.- Before this node, each earlier node was
resultwith chance 1/(i - 1). It staysresultonly when the draw is not 0, which has chance (i - 1)/i. So it keeps 1/(i - 1) * (i - 1)/i = 1/i. - The new node has chance 1/i too. So after
inodes, each of them isresultwith chance 1/i. - After the last node, every node has chance 1/n. The function returns
resultwithout a copy of the list.
Traps
randrange(i + 1)instead ofrandrange(i). The head is taken only half the time. For the list[1, 2], the values 0, 1 and 2 are each returned in one third of the calls, and 0 is not in the list.- Return at the first hit.
randrange(1)is always 0, so the first node always hits. The function returns the head on every call. The loop must continue to the end. - Choose once in
__init__. Every call togetRandomthen returns the same value. Each call needs a new walk and new draws. icounts the wrong things. In Random Pick Index (LC 398),icounts matches, not positions. Otherwise the chances are not equal.iis incremented after the draw. The draw would then use the count before the current node, and at the first noderandrange(0)raisesValueError.