Last updated on January 5th, 2025 at 01:00 am

Here, we see a Random Pick Index LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Reservoir Sampling

Companies

Facebook

Level of Question

Medium

Random Pick Index LeetCode Solution

1. Problem Statement

Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Implement the Solution class:

• Solution(int[] nums) Initializes the object with the array nums.
• int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i’s, then each index should have an equal probability of returning.

Example 1:
Input [“Solution”, “pick”, “pick”, “pick”] [[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output [null, 4, 0, 2]
Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “Reservoir Sampling”. This is a probabilistic algorithm used to randomly select a sample (or index) from a stream or collection of data, ensuring that each element has an equal probability of being chosen.

3. Code Implementation in Different Languages

3.1 Random Pick Index C++

class Solution {
public:
    unordered_map<int,vector<int>> m;
    Solution(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            m[nums[i]].push_back(i);
        }
    }
    int pick(int target) {
        int x=m[target].size();
        x=rand()%x;
        return m[target][x];
    }
};

3.2 Random Pick Index Java

class Solution {
    int[] nums;
    Random random;
    public Solution(int[] nums) {
        this.nums = nums;
        this.random = new Random();
    }
    public int pick(int target) {
        int idx = -1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
                if (random.nextInt(count) == 0) {
                    idx = i;
                }
            }
        }
        return idx;
    }
}

3.3 Random Pick Index JavaScript

var Solution = function(nums) {
    this.nums = nums;
    this.len = nums.length;
};
Solution.prototype.pick = function(target) {
    if (this.len == 1) return 0;
    var result = 0;
    var count = 0;
    for (var i = 0; i < this.len; i++) {
        if (this.nums[i] == target) {
            if (Math.floor(Math.random() * (++count)) == 0) result = i;
        }
    }
    return result;
};

3.4 Random Pick Index Python

class Solution(object):
    def __init__(self, nums):
        self.indices = defaultdict(list)
        for i, num in enumerate(nums):
            self.indices[num].append(i)
    def pick(self, target):
        return random.choice(self.indices[target])

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(1)	O(n)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(1)	O(n)

• The problem uses the Reservoir Sampling pattern.
• C++ and Python use a preprocessing approach with a hash map for fast pick operations.
• Java and JavaScript use Reservoir Sampling to avoid preprocessing, trading off space for time.
• The time complexity for pick is O(1) for C++ and Python, and O(n) for Java and JavaScript. The space complexity is O(n) for C++ and Python, and O(1) for Java and JavaScript.