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.
This approach involves preprocessing the blacklist by sorting it. Upon calling 'pick', we randomly select a number from 0 to n - blacklist.length - 1 and adjust it using binary search to account for blacklisted numbers.
In this Python solution, the 'bisect_left' function is used to find the number of blacklisted numbers less than the current random number, thus adjusting it directly to a safe number.
Time Complexity: O(log B) per pick call, where B is the length of blacklist.
Space Complexity: O(B) due to storage of the blacklist.
This approach involves creating a mapping from blacklisted numbers under n-k (where k is the list length) to valid un-blacklisted numbers above that range. This method efficiently handles cases when n is large but the blacklist is relatively small.
This JavaScript solution initializes the mapping in the constructor, so invalid values in the lower range are mapped to available numbers in the higher ones. The pick method then uses this map to return a correct answer efficiently.
JavaScript
C++
Time Complexity: O(1) per pick call.
Space Complexity: O(B) where B is the size of the blacklist.
| Approach | Complexity |
|---|---|
| Binary Search on Sorted Blacklist | Time Complexity: O(log B) per pick call, where B is the length of blacklist. |
| Hash Map with Mapping | Time Complexity: O(1) per pick call. |
| Default Approach | — |
| 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 |
Random Pick with blacklist || Leetcode • Pepcoding • 3,114 views views
Watch 9 more video solutions →Practice Random Pick with Blacklist with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor