How to Solve Random Pick Index

To solve Random Pick Index, the core idea is to use a hash table to store the indices of each target number and apply reservoir sampling to randomly pick one index. This ensures uniform probability of selecting any of the possible indices for the target. Reservoir sampling provides an elegant solution by updating the chosen index as the function iterates through occurrences of the target number.

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

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.

How GhostInterview Helps

• GhostInterview helps by offering a well-rounded solution for solving Random Pick Index, guiding you through efficient data structures and randomization techniques.
• With GhostInterview's practice environment, you can master hash tables and reservoir sampling while getting insights into optimizing your code for time and space complexity.
• GhostInterview's detailed explanations and guided solution breakdowns ensure you can tackle similar problems with confidence and clarity.

Topic Pages

• Hash Table
• Math
• Reservoir Sampling
• Randomized

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.