Random Pick Index [Reservoir Sampling]

82.Random Pick Index

Array

Math

Reservoir Sampling

Problem Statement:

Given an array of integers nums containing duplicates, implement a class that allows randomly picking an index of a specified target value. Each index of the target should be returned with equal probability.

Algorithm:

1. Initialize the array nums and a random number generator in the constructor.
2. When the pick method is called:
• Traverse through the array and count occurrences of the target.
• For each occurrence, use a random number generator to decide whether to update the result index based on reservoir sampling logic:
• Update the result index with probability 1/count, ensuring each target index has an equal chance of being picked.
3. Return the selected index after the traversal.

Complexity:

Time: O(n) per pick call, where n is the size of the array | Space: O(1)

Java Implementation:

import java.util.Random;

public class Solution {
    int[] nums;
    Random rnd;

    public Solution(int[] nums) {
        this.nums = nums;
        this.rnd = new Random(); // Initialize random number generator
    }
    
    public int pick(int target) {
        int result = -1; // Variable to store the index to be returned
        int count = 0;   // Count occurrences of the target value
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
                // Update result with probability 1/count
                if (rnd.nextInt(count) == 0) {
                    result = i;
                }
            }
        }
        return result; // Return the selected index
    }
}

Python Implementation:

import random

class Solution:
    def __init__(self, nums):
        self.nums = nums

    def pick(self, target):
        result = -1
        count = 0
        
        for i, num in enumerate(self.nums):
            if num == target:
                count += 1
                # Update result with probability 1/count
                if random.randint(1, count) == 1:
                    result = i
        
        return result

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
private:
    vector nums;

public:
    Solution(vector& nums) : nums(nums) {}

    int pick(int target) {
        int result = -1;
        int count = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                count++;
                // Update result with probability 1/count
                if (rand() % count == 0) {
                    result = i;
                }
            }
        }
        return result;
    }
};