398. Random Pick Index – Leetcode Solutions

Example 1:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

class Solution:
    def __init__(self, nums: List[int]):
        """
        Initializes the object with the array nums.
        :param nums: List[int] - Input array
        """
        # Store the array for future reference
        self.nums = nums

    def pick(self, target: int) -> int:
        """
        Picks a random index i from nums where nums[i] == target.
        :param target: int - The target value to search for
        :return: int - A randomly chosen index
        """
        # Collect all indices where nums[i] == target
        target_indices = [i for i, num in enumerate(self.nums) if num == target]
        
        # Randomly pick one of these indices
        return random.choice(target_indices)

class Solution {
private:
    // Map to store the indices of each number in the nums array
    unordered_map<int, vector<int>> index_map;

public:
    // Constructor to initialize the Solution object
    Solution(vector<int>& nums) {
        // Populate the map with indices of each number
        for (int i = 0; i < nums.size(); ++i) {
            index_map[nums[i]].push_back(i);
        }
    }
    
    // Method to pick a random index of the target
    int pick(int target) {
        // Get the vector of indices corresponding to the target number
        const vector<int>& indices = index_map[target];
        
        // Randomly select an index from the vector
        // Use rand() % indices.size() to ensure uniform distribution
        int random_index = rand() % indices.size();
        
        // Return the actual index from the nums array
        return indices[random_index];
    }
};

var Solution = function(nums) {
    // Store the input array in the object for later use
    this.nums = nums;

    // Create a map to store the indices of each number
    this.indexMap = new Map();

    // Populate the index map with indices for each number
    for (let i = 0; i < nums.length; i++) {
        if (!this.indexMap.has(nums[i])) {
            this.indexMap.set(nums[i], []);
        }
        this.indexMap.get(nums[i]).push(i);
    }
};

/** 
 * @param {number} target
 * @return {number}
 */
Solution.prototype.pick = function(target) {
    // Retrieve the indices corresponding to the target number
    const indices = this.indexMap.get(target);

    // Randomly select an index from the array of indices
    const randomIndex = Math.floor(Math.random() * indices.length);

    // Return the selected index
    return indices[randomIndex];
};

class Solution {

    // HashMap to store the indices of each number in the array
    private HashMap<Integer, ArrayList<Integer>> indexMap;
    private Random random;

    // Constructor to initialize the Solution object
    public Solution(int[] nums) {
        // Initialize the HashMap
        indexMap = new HashMap<>();
        
        // Initialize the Random object
        random = new Random();
        
        // Populate the HashMap with indices for each number
        for (int i = 0; i < nums.length; i++) {
            // If the number is not already a key in the map, add it
            indexMap.putIfAbsent(nums[i], new ArrayList<>());
            
            // Append the current index to the list of indices for this number
            indexMap.get(nums[i]).add(i);
        }
    }

    // Method to pick a random index for a given target
    public int pick(int target) {
        // Get the list of indices for the target number from the map
        ArrayList<Integer> indices = indexMap.get(target);
        
        // Generate a random index within the range of the list size
        int randomIndex = random.nextInt(indices.size());
        
        // Return the index at the randomly chosen position
        return indices.get(randomIndex);
    }
}