# Random Pick with Blacklist
**Difficulty:** HARD
[External](https://leetcode.com/problems/random-pick-with-blacklist)
Canonical: https://scaleengineer.com/dsa/problems/random-pick-with-blacklist
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting), [Bloom Filter](https://scaleengineer.com/algorithms/bloom-filter)
**Data structures:** Array, Hash Table
---
## Problem
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 <= 109`
* `0 <= blacklist.length <= min(105, n - 1)`
* `0 <= blacklist[i] < n`
* All the values of `blacklist` are **unique**.
* At most `2 * 104` calls will be made to `pick`.

# Approaches
## Pre-computation of Whitelist (Infeasible)
The most straightforward idea is to generate a list of all valid numbers (the "whitelist") during initialization. The `pick()` method then simply selects a random element from this pre-computed list.
**Time:** Constructor: `O(n + B)`. The loop runs `n` times. Given `n` can be up to 10^9, this is too slow and will cause a "Time Limit Exceeded" error.
`pick()`: `O(1)`. · **Space:** `O(n - B)` to store the `whitelist`, where `B` is the blacklist size. Since `n` can be 10^9, this will cause an "Out of Memory" error.
**Pros:** The `pick()` operation is very fast, O(1).; The logic is simple to understand.
**Cons:** Extremely high time complexity in the constructor, making it infeasible for large `n`.; Extremely high space complexity, making it infeasible for large `n`.
### Explanation
In this approach, we first build a complete list of all numbers that are not in the `blacklist`. This is done once during the initialization of the `Solution` object.

**Constructor (`Solution(n, blacklist)`)**
1.  First, we convert the `blacklist` array into a `HashSet` for efficient O(1) average time lookups. This helps in quickly checking if a number is blacklisted.
2.  We create a new `ArrayList` to store the valid numbers, let's call it `whitelist`.
3.  We then iterate through all numbers from `0` to `n-1`.
4.  For each number `i`, we check if it exists in the `blacklist` `HashSet`.
5.  If `i` is not in the `blacklist`, we add it to our `whitelist` `ArrayList`.

**`pick()` Method**
1.  The size of the `whitelist` is `W`, which is `n - blacklist.length`.
2.  We generate a random integer `index` in the range `[0, W-1]`.
3.  We return the element at `whitelist.get(index)`. All valid numbers are in the list, so picking a random index gives a uniform probability to each valid number.

This approach is simple but fundamentally flawed by the problem's constraints, where `n` can be up to 10<sup>9</sup>.

```java
class Solution {
    private List<Integer> whitelist;
    private Random rand;

    public Solution(int n, int[] blacklist) {
        this.whitelist = new ArrayList<>();
        this.rand = new Random();
        Set<Integer> blacklistSet = new HashSet<>();
        for (int b : blacklist) {
            blacklistSet.add(b);
        }

        for (int i = 0; i < n; i++) {
            if (!blacklistSet.contains(i)) {
                this.whitelist.add(i);
            }
        }
    }

    public int pick() {
        int randomIndex = rand.nextInt(this.whitelist.size());
        return this.whitelist.get(randomIndex);
    }
}
```
### Algorithm
*   Initialize a `HashSet` from the `blacklist` array.
*   Initialize an `ArrayList` `whitelist`.
*   Loop from `i = 0` to `n-1`. If `i` is not in the `blacklist` set, add it to `whitelist`.
*   To `pick`, generate a random index up to `whitelist.size()` and return the element at that index.

## Rejection Sampling
This approach involves generating a random number in the full range `[0, n-1]` and checking if it's in the `blacklist`. If it is, we "reject" it and try again. We repeat this process until we find a number that is not blacklisted.
**Time:** Constructor: `O(B)` to create the `HashSet`.
`pick()`: The expected time complexity is `O(n / (n - B))`. If `B` is much smaller than `n`, this is close to O(1). However, if `B` is close to `n`, this can be very large, potentially leading to a "Time Limit Exceeded" error. · **Space:** `O(B)` to store the `blacklist` in a `HashSet`, where `B` is the blacklist size.
**Pros:** Relatively simple to implement.; Low memory usage compared to the whitelist approach.; Fast constructor.
**Cons:** The `pick()` method's performance is unpredictable and can be very slow if the density of blacklisted numbers is high.; It does not guarantee minimizing the calls to the random function, which is a requirement of the problem.
### Explanation
This method uses a probabilistic technique called rejection sampling. Instead of pre-calculating the valid numbers, we generate a random number from the entire range and check its validity on the fly.

**Constructor (`Solution(n, blacklist)`)**
1.  Store the value of `n`.
2.  Convert the `blacklist` array into a `HashSet` for efficient O(1) average time lookups. This is crucial for the performance of the `pick()` method.

**`pick()` Method**
1.  Enter a loop that continues until a valid number is found.
2.  Inside the loop, generate a random integer `candidate` in the range `[0, n-1]`.
3.  Check if the `candidate` is present in the `blacklist` `HashSet`.
4.  If it's not in the `blacklist`, it's a valid number. Return the `candidate` and exit the loop.
5.  If it is in the `blacklist`, the loop continues, and a new number is generated in the next iteration.

Each number in `[0, n-1]` has an equal chance of being generated. By only returning the non-blacklisted ones, we ensure that every valid number has an equal probability of being chosen.

```java
class Solution {
    private int n;
    private Set<Integer> blacklistSet;
    private Random rand;

    public Solution(int n, int[] blacklist) {
        this.n = n;
        this.rand = new Random();
        this.blacklistSet = new HashSet<>();
        for (int b : blacklist) {
            this.blacklistSet.add(b);
        }
    }

    public int pick() {
        while (true) {
            int candidate = rand.nextInt(n);
            if (!blacklistSet.contains(candidate)) {
                return candidate;
            }
        }
    }
}
```
### Algorithm
*   Store `n` and convert `blacklist` to a `HashSet`.
*   In a loop, generate a random number `r` from `[0, n-1]`.
*   If `r` is not in the `blacklist` set, return `r`.
*   Otherwise, repeat the process.

## Mapping with Virtual Whitelist
This is the optimal approach that addresses the shortcomings of the previous methods, especially the large value of `n`. The core idea is to remap blacklisted numbers that fall within an initial, smaller valid range to valid numbers that fall outside this range. This allows us to pick a random number from a contiguous range and get a valid, uniformly distributed result with a single random call.
**Time:** Constructor: `O(B)`, where `B` is the length of the `blacklist`. We iterate through the blacklist a constant number of times. The `while` loop's pointer `p` only ever increases and is incremented at most `B` times in total. Thus, the total time is `O(B)`.
`pick()`: `O(1)` on average, as it involves a random number generation and a hash map lookup. · **Space:** `O(B)` to store the mapping and the set of tail-end blacklisted numbers. The size of the map is at most `B`.
**Pros:** Optimal `pick()` performance: `O(1)` time.; Guarantees a single call to the random number generator per `pick()`.; Efficient constructor `O(B)` that handles large `n` correctly.; Memory usage is proportional to the size of the blacklist, not `n`.
**Cons:** The logic is more complex to reason about and implement correctly compared to simpler approaches.
### Explanation
Let `B` be the size of the `blacklist`. The number of whitelisted (valid) integers is `W = n - B`. Our goal is to pick a random number from these `W` valid integers. We can do this by generating a random index `k` in the range `[0, W-1]` and mapping this index to a unique valid number.

The numbers in the range `[0, W-1]` are our initial candidates. However, some of these candidates might be in the `blacklist`. The key insight is that the number of blacklisted values in `[0, W-1]` is equal to the number of whitelisted values in `[W, n-1]`. We can therefore create a mapping: for every blacklisted number `b < W`, we find a unique whitelisted number `v >= W` and map `b` to `v`.

**Constructor (`Solution(n, blacklist)`) Algorithm:**
1.  Calculate the size of the whitelist: `W = n - blacklist.length`.
2.  Create a `HashSet`, `tailBlacklist`, containing all blacklisted numbers that are greater than or equal to `W`. This helps us quickly find valid numbers in the tail section `[W, n-1]`.
3.  Create a `HashMap`, `mapping`, to store the remappings.
4.  Initialize a pointer `p` to `W`. This pointer will scan for available whitelisted numbers in the tail section.
5.  Iterate through each number `b` in the original `blacklist`. If `b` is less than `W`, we need to remap it.
6.  To find a replacement for `b`, we use our pointer `p`. We advance `p` until we find a number that is not in `tailBlacklist`.
7.  Once we find such a valid number `p`, we create the mapping `mapping.put(b, p)` and increment `p`.

**`pick()` Method Algorithm:**
1.  Generate a random integer `k` in the range `[0, W-1]`.
2.  If `k` is a key in our `mapping`, it means `k` was a blacklisted number. We return its mapped value: `mapping.get(k)`.
3.  Otherwise, `k` was a valid number in `[0, W-1]` to begin with, so we return `k`.

This ensures that any pick from `[0, W-1]` results in a unique valid number, and all `W` valid numbers have an equal chance of being chosen.

```java
class Solution {
    private Map<Integer, Integer> mapping;
    private int whitelistSize;
    private Random rand;

    public Solution(int n, int[] blacklist) {
        this.mapping = new HashMap<>();
        this.rand = new Random();
        this.whitelistSize = n - blacklist.length;

        // Store blacklisted numbers >= whitelistSize in a set for fast lookup.
        Set<Integer> tailBlacklist = new HashSet<>();
        for (int b : blacklist) {
            if (b >= this.whitelistSize) {
                tailBlacklist.add(b);
            }
        }

        int p = this.whitelistSize;
        for (int b : blacklist) {
            if (b < this.whitelistSize) {
                // Find the next available whitelisted number in the tail.
                while (tailBlacklist.contains(p)) {
                    p++;
                }
                // Map the blacklisted number `b` to the whitelisted number `p`.
                this.mapping.put(b, p);
                p++;
            }
        }
    }

    public int pick() {
        int k = rand.nextInt(this.whitelistSize);
        // If k is a remapped blacklisted number, return its new value.
        // Otherwise, k is a valid number itself.
        return this.mapping.getOrDefault(k, k);
    }
}
```
### Algorithm
*   Calculate `W = n - blacklist.length`.
*   Partition the `blacklist` into numbers `< W` and numbers `>= W`. Store the latter in a `HashSet`.
*   Initialize a pointer `p = W`.
*   For each blacklisted number `b < W`, find the smallest number `v >= p` that is not in the blacklist set. Map `b` to `v` and update `p = v + 1`.
*   To `pick`, generate a random number `k` in `[0, W-1]`. If `k` is in the map, return its mapped value. Otherwise, return `k`.

# Solutions
### Java

```java
class Solution { private Map < Integer , Integer > d = new HashMap <>(); private Random rand = new Random (); private int k ; public Solution ( int n , int [] blacklist ) { k = n - blacklist . length ; int i = k ; Set < Integer > black = new HashSet <>(); for ( int b : blacklist ) { black . add ( b ); } for ( int b : blacklist ) { if ( b < k ) { while ( black . contains ( i )) { ++ i ; } d . put ( b , i ++); } } } public int pick () { int x = rand . nextInt ( k ); return d . getOrDefault ( x , x ); } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(n, blacklist); * int param_1 = obj.pick(); */
```

### CPP

```cpp
class Solution { public: unordered_map < int , int > d ; int k ; Solution ( int n , vector < int >& blacklist ) { k = n - blacklist . size (); int i = k ; unordered_set < int > black ( blacklist . begin (), blacklist . end ()); for ( int & b : blacklist ) { if ( b < k ) { while ( black . count ( i )) ++ i ; d [ b ] = i ++ ; } } } int pick () { int x = rand () % k ; return d . count ( x ) ? d [ x ] : x ; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(n, blacklist); * int param_1 = obj->pick(); */
```

### Python

```python
class Solution : def __init__ ( self , n : int , blacklist : List [ int ]): self . k = n - len ( blacklist ) self . d = {} i = self . k black = set ( blacklist ) for b in blacklist : if b < self . k : while i in black : i += 1 self . d [ b ] = i i += 1 def pick ( self ) -> int : x = randrange ( self . k ) return self . d . get ( x , x ) # Your Solution object will be instantiated and called as such: # obj = Solution(n, blacklist) # param_1 = obj.pick()
```