Python solution with detailed explanation


  • 1
    G

    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
    

  • 0
    L

    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.


  • 0
    G

    @livelearn Using your example:
    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


  • 0

    @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 :-)


  • 0
    G

    @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.


Log in to reply
 

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