Watch 10 video solutions for Random Pick with Blacklist, a hard level problem involving Array, Hash Table, Math. This walkthrough by Pepcoding has 3,114 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1] that is not in blacklist. Any integer that is in the mentioned range and not in blacklist should be equally likely to be returned.
Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language.
Implement the Solution class:
Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist.int pick() Returns a random integer in the range [0, n - 1] and not in blacklist.
Example 1:
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 <= 1090 <= blacklist.length <= min(105, n - 1)0 <= blacklist[i] < nblacklist are unique.2 * 104 calls will be made to pick.Problem Overview: You need to randomly return an integer from the range [0, n) while excluding numbers listed in a blacklist. Every valid number must have equal probability. The challenge is avoiding blacklisted values without repeatedly generating random numbers and rejecting them.
Approach 1: Binary Search on Sorted Blacklist (Pick: O(log b), Preprocess: O(b log b))
Sort the blacklist first. Instead of picking from [0, n), pick a random index k from the range [0, n - b) where b is the blacklist size. This represents the index of the k-th valid number if the blacklist didn’t exist. Use binary search on the sorted blacklist to determine how many blacklisted numbers are less than or equal to the candidate value and shift the result accordingly. The key insight: each blacklisted value "pushes" valid numbers forward. Binary search efficiently finds how many pushes occur. Sorting dominates preprocessing at O(b log b), and each random pick costs O(log b). Space complexity is O(b). This approach relies on binary search and works well when the blacklist is static.
Approach 2: Hash Map with Remapping (Pick: O(1), Preprocess: O(b))
The optimal solution remaps blacklisted values that fall inside the valid picking range. Let m = n - b. Generate random numbers only from [0, m). If a blacklisted number appears inside this range, map it to a safe number from the upper range [m, n) that is not blacklisted. Build a hash map where each blocked value in the lower range points to a valid replacement. During pick(), generate a random integer x in [0, m). If x exists in the map, return the mapped value; otherwise return x. Preprocessing scans the blacklist and uses a set or map for constant-time checks, resulting in O(b) time and space. Each random pick runs in O(1). This method heavily uses hash tables and randomized selection concepts from randomized algorithms. It guarantees uniform distribution across valid numbers.
Recommended for interviews: The hash map remapping approach is what most interviewers expect because it achieves O(1) pick time while keeping preprocessing linear. Explaining the binary search idea first shows you understand the indexing trick of skipping blacklisted values. Implementing the remapping solution demonstrates strong command of array indexing, hashing, and probability correctness.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Sorted Blacklist | Preprocess: O(b log b), Pick: O(log b) | O(b) | When the blacklist is static and binary search logic is acceptable for each pick |
| Hash Map with Remapping | Preprocess: O(b), Pick: O(1) | O(b) | Best general solution when frequent random picks are required |