Python solution with detailed explanation

• Solution

Random Pick Index https://leetcode.com/problems/random-pick-index/

• Do we want to optimize run time or memory?If we want to optimize run time then we can use a dictionary to pre-process the nums array. Simply create a map of key (number) and value (list of its indices). Then run reservoir sampling over this input.
• But the problem statement says that using too much memory is not allowed. In that case, we can iterate the entire array and keep a variable to track the frequency of the target for input into reservoir sampling.
• Notice random() returns uniform random number between [0 to 1]
``````from random import random
class Solution(object):
def __init__(self, nums):
"""
:type nums: List[int]
:type numsSize: int
"""
self.nums = nums

def pick(self, target):
"""
:type target: int
:rtype: int
"""
cnt, index = 0, 0
for idx, x in enumerate(self.nums):
if x == target:
cnt += 1
if random() <= 1.0/(cnt):
index = idx
return index
``````

• Technically you don't have an equal likelihood of picking each element.
Consider 123.
First 1 gets entered into our reservoir.
Now choose between 2 and 1, let's pick 1 over 2: so in our reservoir we only have 1.
When 3 enters we have a 2/3 chance of picking 1 and a 1/3 chance of picking 3, but a 0 chance of picking 2. Meaning moving forward, there is no chance of getting 2. A correct reservoir sampling solution would keep track of all the options that haven't been accepted and possible bring one of those elements in.

P(1 is finally selected) = P(1 is selected) and P(2 is not selected) and P(3 is not selected) = 1 * 1/2 * 2/3 = 1/3

P(2 is finally selected) = P(2 is selected) and P(3 is not selected) = 1/2 * 2/3 = 1/3

P(3 is finally selected) = P(2 is selected) and P(3 is selected) + P(2 is not selected) and P(3 is selected) = 1/3

• @gabbu

In line 1 you say P(2 is not selected) is 1/2 and in line 2 you say P(2 is selected) is 1/3. But "not selected" and "selected" should add up to 1.

Better use different terminology for the two kinds of being "selected".

And P(3 is selected) is simply P(3 is selected) is simply 1/3. No need to involve P(2 ...) and not explain how you get to 1/3.

Btw, @jy04472052 already showed what you showed and apparently it didn't help at all. Well, maybe the repetition helps :-)

• @StefanPochmann Thanks - I made it "finally selected". Doesn't hurt to lay out both the paths (select 2 or not select 2) to finally select 3 - I think that would help someone having an issue how probabilities work in this problem.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.