398. Random Pick Index

Description

Given an array of integers, we need to pick an index at random from the array where a given target number appears. The key challenge is to ensure each target number is picked with equal probability, even when the target appears multiple times in the array.

Intuition

To ensure equal probability of picking any occurrence of the target, we can use a reservoir sampling technique. As we iterate over the array and encounter each instance of the target, we randomly decide whether to select this index, progressively reducing the likelihood as more instances are encountered.

Approach

1. Initialize a result res as -1 and a count to keep track of how many times the target has been seen.
2. Loop through the array: - Each time the target is found, increase the count and pick the current index with probability 1/count. - Use randomization to decide whether to update res to the current index.
3. Return the chosen index after iterating through the array.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array.

Space Complexity:

O(1), excluding the input array, as only a few extra variables are used.

Code

C++

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

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */

Python

class Solution:

    def __init__(self, nums: list[int]):
        self.nums = nums

    def pick(self, target: int) -> int:
        res = -1
        count = 0
        for i, num in enumerate(self.nums):
            if num == target:
                count += 1
                if random.randint(0, count - 1) == 0:
                    res = i
        return res

Java

class Solution {
    private int[] nums;
    private Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        this.random = new Random();
    }

    public int pick(int target) {
        int res = -1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
                if (random.nextInt(count) == 0) {
                    res = i;
                }
            }
        }
        return res;
    }
}


/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

JavaScript

var Solution = function(nums) {
    this.num = nums;
};
/** 
 * @param {number} target
 * @return {number}
 */
Solution.prototype.pick = function(target) {
    let res = -1, count = 0;
    for(let i = 0; i < this.num.length; i++) {
        if(this.num[i] === target) {
            count++;
            if(Math.floor(Math.random() * count) === 0) {
               res = i;
            }
        }
        
    }
    return res;
};