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.

```java
class Solution {
int size;
Set

```
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(); */```