{x}
blog image

Random Pick Index

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.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1
  • target is an integer from nums.
  • At most 104 calls will be made to pick.

Solution Explanation: Reservoir Sampling

This problem asks to randomly pick an index from a list where the element at that index equals a given target value. The solution uses Reservoir Sampling, a randomized algorithm to select a sample of k elements from a list of n elements, where n is not known in advance. In this case, k = 1.

Algorithm:

  1. Initialization: We initialize n (the count of occurrences of the target) and ans (the index to be returned) to 0.

  2. Iteration: We iterate through the input array nums.

  3. Target Check: If an element v equals the target:

    • Increment n.
    • Generate a random integer x between 1 and n (inclusive).
    • If x equals n, update ans to the current index i. This step ensures that each index with the target value has an equal probability of being selected.

  4. Return: After iterating through the entire array, we return ans.

Why this works (Reservoir Sampling):

The key is the probability at each step. Let's say we've encountered m occurrences of the target. The probability that we choose a specific index among these m is 1/m. When we encounter the m+1th occurrence, the probability that we retain the previously selected index is m/(m+1), and the probability of selecting the new index is 1/(m+1). This ensures that every index has an equal probability of being chosen by the end of the process.

Time Complexity: O(N), where N is the length of the input array nums. We iterate through the array once.

Space Complexity: O(1). We use only a few constant extra variables.

Code Examples (with explanations inline):

The code examples provided are all efficient implementations of this reservoir sampling approach. Let's examine the Python version in more detail:

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
 
    def pick(self, target: int) -> int:
        n = ans = 0  # Initialize count of targets and selected index
        for i, v in enumerate(self.nums): # Iterate with index
            if v == target:
                n += 1  # Increment target count
                x = random.randint(1, n) # Generate random number 1 to n
                if x == n: # If random number equals current count, select index
                    ans = i  # Update selected index
        return ans # Return the selected index

The Java, C++, and Go versions follow the same logic, only differing in syntax and random number generation methods. For example, Java uses java.util.Random, while C++ uses rand(), and Go uses rand.Intn(). They all maintain the same time and space complexity.