Random Pick Index - Solution & Explanation
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 arraynums.int pick(int target)Picks a random indexifromnumswherenums[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 - 1targetis an integer fromnums.- At most
104calls will be made topick.
Approach Overview
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.
Approach 1: Simple Random Selection with Array
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.
Code
Python
C++
Java
C#
JavaScript
Complexity
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.
Approach 2: Reservoir Sampling
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.
Code
Python
C++
Java
C#
JavaScript
Complexity
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 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
RANDOM PICK INDEX | LEETCODE # 398 | PYTHON RESERVOIR SAMPLING • Cracking FAANG • 13,935 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Random Pick Index easy or hard?
How to solve Random Pick Index in O(n)?
What is the best approach for Random Pick Index?
Is Random Pick Index asked at Google/Amazon/Meta?
What data structure is used in Random Pick Index?
What is the time complexity of Random Pick Index?
Random Pick Index Python or Java solution approach?
Ready to solve this problem?
Practice Random Pick Index with our built-in code editor and test cases.
Practice on FleetCode