Random Pick Index — Reservoir Sampling

Problem 194 · Random Pick Index

Difficulty: Medium · Pattern: Reservoir Sampling

Given an array (possibly with duplicates), pick a random index of a target value with equal probability.

Intuition

Reservoir sampling: iterate through array; when nums[i] == target, increment count and replace result with probability 1/count.

Solutions

# Python
import random
class Solution:
    def __init__(self, nums): self.nums = nums
    def pick(self, target):
        count = 0; res = -1
        for i, x in enumerate(self.nums):
            if x == target:
                count += 1
                if random.randint(1, count) == 1:
                    res = i
        return res

// Java
class Solution {
    int[] nums;
    Random rand = new Random();
    public Solution(int[] nums) { this.nums = nums; }
    public int pick(int target) {
        int count = 0, res = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target && rand.nextInt(++count) == 0)
                res = i;
        }
        return res;
    }
}

// C++
class Solution {
    vector<int> nums;
public:
    Solution(vector<int>& nums) : nums(nums) {}
    int pick(int target) {
        int count = 0, res = -1;
        for (int i = 0; i < (int)nums.size(); i++)
            if (nums[i] == target && rand() % ++count == 0)
                res = i;
        return res;
    }
};

Complexity

Time: O(n) per pick
Space: O(1) extra (O(n) for array)

Key Insight

Reservoir sampling guarantees each valid index is selected with equal probability 1/k where k = count of target.