To solve Random Pick with Blacklist, map blacklisted numbers in the upper range to valid indices using a hash table. This allows O(1) random access while skipping blacklisted entries. The method minimizes calls to the random function and ensures uniform probability among non-blacklisted integers.
Problem Statement
You are given an integer n and a unique integer array blacklist. Design a data structure that allows picking a random integer from [0, n - 1] that is not present in blacklist. Each valid integer should have an equal chance of being returned on each call.
Optimize the implementation to minimize the number of calls to the built-in random generator. Implement a class Solution with a constructor accepting n and blacklist, and a pick() method that returns a valid random integer efficiently, even when blacklist is large.
Examples
Example 1
Input: See original problem statement.
Output: See original problem statement.
Input ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []] Output [null, 0, 4, 1, 6, 1, 0, 4]
Explanation Solution solution = new Solution(7, [2, 3, 5]); solution.pick(); // return 0, any integer from [0,1,4,6] should be ok. Note that for every call of pick, // 0, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/4). solution.pick(); // return 4 solution.pick(); // return 1 solution.pick(); // return 6 solution.pick(); // return 1 solution.pick(); // return 0 solution.pick(); // return 4
Constraints
- 1 <= n <= 109
- 0 <= blacklist.length <= min(105, n - 1)
- 0 <= blacklist[i] < n
- All the values of blacklist are unique.
- At most 2 * 104 calls will be made to pick.
Solution Approach
Map Blacklisted Values
Use a hash table to map blacklisted numbers in the lower range to valid numbers in the upper range. This allows skipping blacklisted indices while maintaining O(1) pick time.
Random Selection Within Valid Range
Generate a random integer between 0 and n - blacklist.length - 1. If the value maps to a blacklisted index, use the precomputed hash mapping to get a valid integer.
Optimize for Space and Calls
Only store mappings for blacklisted numbers that fall in the random selection range. This reduces space usage and minimizes the number of random function calls required.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(1) per pick after O(B) preprocessing where B is the blacklist length. Space complexity is O(B) for the hash map storing remapped values.
What Interviewers Usually Probe
- Emphasize minimizing random function calls while ensuring uniform distribution.
- Check if the candidate maps blacklisted indices correctly instead of scanning every time.
- Look for clear reasoning on hash map usage and upper-lower range mapping.
Common Pitfalls or Variants
Common pitfalls
- Attempting to randomly pick and retry until valid, which is inefficient for large n and blacklist.
- Not mapping blacklisted numbers that fall in the random pick range, leading to incorrect probabilities.
- Overusing space by mapping all blacklist numbers instead of only those needed for O(1) access.
Follow-up variants
- Pick multiple random integers without replacement while respecting the blacklist.
- Blacklist is dynamic and can change between picks, requiring dynamic remapping.
- Support weighted random picks among non-blacklisted numbers instead of uniform selection.
How GhostInterview Helps
- Automatically generates hash mapping strategies for the pick range, reducing manual setup.
- Verifies uniform distribution of picked numbers to ensure correct probability handling.
- Highlights common pitfalls like naive retry loops or unnecessary full-array scans.
Topic Pages
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
How does Random Pick with Blacklist differ from standard random selection?
Standard random selection picks any integer uniformly. Here, the algorithm must exclude blacklisted integers while keeping each valid number equally likely.
Why use a hash map for blacklist remapping?
It allows O(1) access to map blacklisted indices in the pick range to valid integers, ensuring efficient and uniform random picks.
Can this method handle very large n?
Yes, since the approach only stores mappings for blacklisted numbers in the random range, space remains O(blacklist.length) regardless of n.
What happens if the blacklist is empty?
The algorithm simplifies to a standard random pick from 0 to n - 1, and no hash mapping is required.
Is the random selection truly uniform?
Yes, the remapping ensures each non-blacklisted integer in [0, n - 1] has an equal probability of being returned on each pick.
Need direct help with Random Pick with Blacklist instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Random Pick with Blacklist from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the missing number in an array containing distinct numbers in the range [0, n].
Open problem page#792 Number of Matching SubsequencesGiven a string s and a list of words, count how many words are subsequences of s using efficient array scanning and hash lookup.
Open problem page#532 K-diff Pairs in an ArraySolve K-diff Pairs in an Array by counting unique differences with a hash map or sorted two-pointer sweep.
Open problem page