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 - 1target is an integer from nums.104 calls will be made to pick.Problem Overview: You receive an integer array where the same value may appear multiple times. When pick(target) is called, return a random index where the target occurs. If the target appears multiple times, every valid index must have the same probability of being chosen.
Approach 1: Simple Random Selection with Array (Preprocessing Hash Map) (Time: O(n) build, O(1) pick | Space: O(n))
Store every index of each number during initialization. Use a hash table where the key is the value and the value is a list of indices where it appears. When pick(target) is called, retrieve the index list and generate a random number within its range. Return the element at that random position. The key insight is that precomputing positions converts the selection step into constant time. This approach works well when you expect many pick calls after initialization and memory usage is not a concern.
Approach 2: Reservoir Sampling (Time: O(n) per pick | Space: O(1))
When extra memory is restricted or the array is extremely large, reservoir sampling provides a clean solution. Iterate through the array and track how many times the target has been seen. Each time the target appears, generate a random number between 1 and the current count. Replace the stored result if the random value equals 1. This guarantees that every valid index has equal probability of selection without storing all positions. The technique comes from streaming algorithms and fits problems involving randomized algorithms with unknown or large datasets.
Recommended for interviews: Reservoir Sampling is typically the expected solution because it demonstrates understanding of probability and space optimization. The hash map approach is easier to implement and often acceptable if multiple queries are expected. Showing both approaches signals strong problem-solving range: first identify the straightforward preprocessing method, then optimize space using probabilistic sampling.
This approach involves traversing the entire array to collect all the indices of the given target. Once we have the indices, we can randomly select one of the indices using a random number generator. This approach is straightforward but can be less efficient if the target picking operation is frequently called.
The Python solution uses a list comprehension to store all the indices of the target in the list indices. Then, it uses random.choice() to randomly pick and return one of these indices.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) for each pick operation, where n is the number of elements in nums since we traverse the array to gather indices.
Space Complexity: O(n) to store the indices of the target.
Reservoir sampling is a technique to randomly choose a sample of k items from a list of n items, where n is either a very large or unknown number. It's useful in our context to allow random selection with a single pass over the data.
The reservoir sampling technique is applied here by incrementing the count each time the target is encountered. We then choose to reset result to the current index with probability 1/count.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) for each pick operation, where n is the size of the array.
Space Complexity: O(1) as no extra data structures proportional to input size are used.
| Approach | Complexity |
|---|---|
| Simple Random Selection with Array | Time Complexity: O(n) for each pick operation, where n is the number of elements in |
| Reservoir Sampling | Time Complexity: O(n) for each pick operation, where n is the size of the array. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Random Selection with Array (Hash Map) | O(n) preprocessing, O(1) per pick | O(n) | Best when many pick calls occur and extra memory is acceptable |
| Reservoir Sampling | O(n) per pick | O(1) | When memory is constrained or the array cannot store all indices |
RANDOM PICK INDEX | LEETCODE # 398 | PYTHON RESERVOIR SAMPLING • Cracking FAANG • 13,736 views views
Watch 9 more video solutions →Practice Random Pick Index with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor