#398

Medium

LeetCode Problem Workspace

Random Pick Index

Random Pick Index involves selecting a random index of a target number in an array with possible duplicates.

hash table math reservoir sampling randomized

Problem Statement

You are given an integer array nums that may contain duplicates, and you need to randomly output the index of a specified target number. It is guaranteed that the target number always exists in the array. Your task is to implement the Solution class with a method pick that, given a target number, selects one of its indices at random, with all indices having an equal probability of being chosen.

The class Solution should be implemented such that the pick method is called multiple times, each time with the target number as an argument. The pick method should return the index of the target number in the array in a randomized manner. The solution should handle multiple calls efficiently.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 Approach

Use a Hash Table to Store Indices

A hash table (or dictionary) stores all indices of each target number in the array. This allows efficient retrieval of the target indices during each pick call. Each key in the hash table corresponds to a target number, and its associated value is a list of indices where the target number occurs.

Apply Reservoir Sampling

Once all target indices are gathered, reservoir sampling is applied to randomly select an index. During the iteration over the target indices, we choose one index randomly, with the probability of picking each one remaining equal. Reservoir sampling ensures that no index is favored over another.

Efficient `pick` Method

The pick method uses the hash table to retrieve the list of indices for the target number and then applies the reservoir sampling technique to return a random index. The space complexity is O(n) for storing the indices, and the time complexity for picking an index is O(1) due to direct hash table access.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The space complexity is O(n) because the solution requires storing the indices of each target number in the hash table. The time complexity for calling pick is O(1) since it directly accesses the list of indices for the target number, and the random selection of an index is done in constant time using reservoir sampling.

What Interviewers Usually Probe

The candidate should demonstrate understanding of efficient random selection techniques.
Look for clear explanation of hash table usage for storing indices.
Evaluate how well the candidate explains reservoir sampling and its role in equal probability selection.

Common Pitfalls or Variants

Common pitfalls

Failing to use a hash table for efficient index retrieval.
Incorrectly implementing random selection without equal probability for each index.
Not accounting for multiple calls to pick and how to handle them efficiently.

Follow-up variants

Add constraints that limit the number of indices for each target.
Implement the solution with a different random selection method, such as using random numbers and modulo operations.
Explore how this approach can be extended to support multi-dimensional arrays or lists of lists.

FAQ

What is the main approach used to solve Random Pick Index?

The main approach uses a hash table to store indices of the target number and reservoir sampling to randomly select one index from them.

How does reservoir sampling work in this problem?

Reservoir sampling ensures that each index for the target number has an equal probability of being selected, even when there are multiple occurrences in the array.

What is the time complexity for each call to `pick`?

The time complexity for each call to pick is O(1), as it involves retrieving indices from the hash table and selecting a random one.

Can this problem be solved without a hash table?

While it is theoretically possible to use a brute force approach, using a hash table provides a more efficient solution, especially when there are multiple calls to pick.

What are the space and time complexities of the solution?

The space complexity is O(n) for storing the indices, and the time complexity is O(1) for each pick call due to efficient hash table access and random selection.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def pick(self, target: int) -> int:
        n = ans = 0
        for i, v in enumerate(self.nums):
            if v == target:
                n += 1
                x = random.randint(1, n)
                if x == n:
                    ans = i
        return ans


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)

Continue Practicing

#519 random flip matrix #382 linked list random node #381 insert delete getrandom o1 duplicates allowed