Formatted question description: https://leetcode.ca/all/710.html
710. Random Pick with Blacklist
Level
Hard
Description
Given a blacklist B
containing unique integers from [0, N)
, write a function to return a uniform random integer from [0, N)
which is NOT in B
.
Optimize it such that it minimizes the call to system’s Math.random()
.
Note:
1 <= N <= 1000000000
0 <= B.length < min(100000, N)
[0, N)
does NOT include N. See interval notation.
Example 1:
Input:
[“Solution”,”pick”,”pick”,”pick”]
[[1,[]],[],[],[]]
Output: [null,0,0,0]
Example 2:
Input:
[“Solution”,”pick”,”pick”,”pick”]
[[2,[]],[],[],[]]
Output: [null,1,1,1]
Example 3:
Input:
[“Solution”,”pick”,”pick”,”pick”]
[[3,[1]],[],[],[]]
Output: [null,0,0,2]
Example 4:
Input:
[“Solution”,”pick”,”pick”,”pick”]
[[4,[2]],[],[],[]]
Output: [null,1,3,1]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution
’s constructor has two arguments, N
and the blacklist B
. pick
has no arguments. Arguments are always wrapped with a list, even if there aren’t any.
Solution
Given an integer N
and a blacklist B
, there are N  B.length
numbers that can be selected. For example, if N
is 100 and B.length
is 10, then there are 100  10 = 90 numbers that can be selected. Therefore, call Math.random()
so that the returned integer is in the range [0, N  B.length)
.
For each number in the blacklist, it is either less than N  B.length
or greater than or equal to N  B.length
. If a number in the blacklist is less than N  B.length
, then it should be mapped to a number in the range [N  B.length, N)
which is not in the blacklist.
In the class, maintain size
which is the number of integers that can be selected, maintain a set to store the numbers in the blacklist, and maintain a map.
For the constructor, initialize size = N  B.length
, and add all the numbers in the blacklist to the set. Then for each number in the blacklist, map it to num
which is in the range [size, N)
and is not in the blacklist (num
is updated after each mapping), with the map updated.
For the method pick
, randomly select an integer in the range [0, size)
, get the corresponding integer from the map (if the integer is not in the map, then the integer remains unchanged), and return the integer.

class Solution { int size; Set<Integer> blacklistSet; Map<Integer, Integer> map; public Solution(int N, int[] blacklist) { size = N  blacklist.length; blacklistSet = new HashSet<Integer>(); for (int blacklistNum : blacklist) blacklistSet.add(blacklistNum); map = new HashMap<Integer, Integer>(); int num = size; for (int blacklistNum : blacklist) { if (blacklistNum < size) { while (blacklistSet.contains(num)) num++; map.put(blacklistNum, num); num++; } } } public int pick() { int num = (int) (Math.random() * size); num = map.getOrDefault(num, num); return num; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(N, blacklist); * int param_1 = obj.pick(); */

// OJ: https://leetcode.com/problems/randompickwithblacklist/ // Time: // Solution: O(BlogB) // pick: O(1) // Space: O(B) class Solution { unordered_map<int, int> m; int len; public: Solution(int n, vector<int>& B) { len = n  B.size(); sort(begin(B), end(B)); int j = lower_bound(begin(B), end(B), len)  begin(B), N = B.size(), next = len; for (int i = 0; i < N && B[i] < len; ++i) { while (j < N && B[j] == next) ++j, ++next; m[B[i]] = next++; } } int pick() { int r = rand() % len; return m.count(r) ? m[r] : r; } };

print("Todo!")