398. Random Pick Index
Model: qwen3.5:9b
Topics: Reservoir Sampling
FAANG asked: 1
Acceptance rate: 58.3%
Problem Breakdown
We are building a class that needs to support two operations: initialization with an array and random selection of indices for specific values. The core requirement is uniform probability—if there are three 3s in the array, picking index i, j, or k must be equally likely (1/3 chance each).
Inputs:
- An integer array
nums. - A target integer value to search for during queries.
Outputs:
- The class constructor initializes state based on
nums. - The method returns a single integer index where the target resides.
Constraints & Edge Cases:
- Duplicates: This is the critical constraint. We cannot just return any random index; we must filter for indices matching the value and ensure uniform distribution among them.
- Existence Guarantee: The problem states
targetalways exists innums, so we don’t need to handle a “not found” case (no null check needed). - Performance: We have up to calls to
pick. If the array is large (), scanning it every time would be too slow ( per call calls = total). We need an efficient lookup. - Memory: Storing indices for all elements fits well within standard memory limits given the constraints, so we don’t strictly need to optimize space aggressively unless specified otherwise (e.g., streaming input), but it’s good practice to discuss trade-offs.
Intuition
The naive approach is to scan nums every time pick(target) is called. We iterate through the array until we find a match, then randomly select one from all matches found so far? No, that doesn’t work for uniform probability without storing them first or using Reservoir Sampling.
Actually, if we don’t store indices:
- Scan: Iterate
numsto collect valid indices (takes ). - Pick: Randomly choose from the collected list ( relative to count of matches, but collection is costly). Total time per call becomes . With many calls, this leads to Time Limit Exceeded (TLE).
Key Insight: Since nums never changes after initialization, we can pre-process it. We should store the indices for every unique number in a hash map during construction. This shifts the cost from query time () to initialization time (), which is acceptable since is fixed and small enough.
This transforms pick into an operation (assuming constant-time random selection). We do not need Reservoir Sampling here because we have sufficient memory to store all indices upfront; pre-computation provides faster query times than streaming algorithms would in this static context.
Approach
- Initialization (
__init__): Create a dictionary (hash map) where keys are values fromnumsand values are lists containing all valid indices found so far. Iterate throughnums, appending the current index to the corresponding list in our map. - Query (
pick): Retrieve the pre-stored list of indices for the giventarget. Since we know it exists, simply use a random number generator (like Python’srandom.choice) to pick one element from that specific list and return its value.
Complexity Analysis
- Time:
- Initialization: where is length of
nums(single pass). - Pick Operation: average case, as dictionary lookup and random choice are constant time relative to input size (random access in a list does not depend on the total array size , only memory locality which is effectively constant for this scale).
- Total for calls: . Given constraints (, ), this is highly efficient.
- Initialization: where is length of
- Space:
- We store every index in the map. In the worst case (all elements unique or all duplicates of one value), we use space to store indices plus dictionary overhead. This fits well within memory limits for these constraints.
Solution
import random
from collections import defaultdict
class Solution:
def __init__(self, nums):
"""
:type nums: List[int]
:rtype: void
Initialize the object with an array of integers.
Pre-process to store indices for each unique number.
"""
self.indices = defaultdict(list)
# Iterate once through nums to build our index map
for i, num in enumerate(nums):
self.indices[num].append(i)
def pick(self, target: int) -> int:
"""
:type target: int
:rtype: int
Return a random index of the given number.
Each valid index has equal probability.
"""
# Retrieve list of indices for this specific value
candidates = self.indices[target]
# Randomly select one from pre-stored candidates
return random.choice(candidates)
Edge Cases Handled
- Multiple Duplicates: The
defaultdict(list)approach naturally handles this by appending every occurrence’s index to the list. Random choice ensures uniform probability across all occurrences (e.g., if there are three ‘3’s, each has a 1/3 chance). - Single Element Array: If
numsis[5], map stores{5: [0]}. Pick returns0. Correct. - Large Input Size (): The initialization and dictionary overhead are well within memory limits for typical LeetCode environments (usually ~MBs of RAM available). Python’s integer objects handle the values without overflow issues as per standard language behavior.