Watch 10 video solutions for Random Pick Index, a medium level problem involving Hash Table, Math, Reservoir Sampling. This walkthrough by Techdose has 37,875 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |