Formatted question description: https://leetcode.ca/all/710.html

# 710. Random Pick with Blacklist

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. 1 <= N <= 1000000000
2. 0 <= B.length < min(100000, N)
3. [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,],[],[],[]]

Output: [null,0,0,2]

Example 4:

Input:

[“Solution”,”pick”,”pick”,”pick”]

[[4,],[],[],[]]

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.

java class Solution { int size; Set blacklistSet; Map<Integer, Integer> map;

public Solution(int N, int[] blacklist) {
size = N - blacklist.length;
blacklistSet = new HashSet<Integer>();
for (int blacklistNum : blacklist)
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(); */