Easy to Understand Hash Table Solution [Python3]
IntuitionMap blacklisted elements withing the valid range i.e. [0, n-len(blacklist)) to outside white (== !black) numbers. Then sample integers from [0, n-len(b
# Intuition
Map blacklisted elements withing the valid range i.e. `[0, n-len(blacklist))` to outside `white (== !black)` numbers. Then sample integers from `[0, n-len(blacklist))`.

# Approach
Let's say n = 10 and blacklist = [3, 5, 8, 9]

valid_size = 10 - 4 = 6
The valid numbers are [0, 1, 2, 4, 6, 7]
Of the blacklisted numbers, [3, 5] are in the range [0, 5], so they need mapping
The valid numbers in range [6, 9] are [6, 7], so we map:

3 → 7
5 → 6


Our mapping dictionary is {3: 7, 5: 6}
When we call pick():

We generate a random number in [0, 5]
If we get 0, 1, 2, or 4, we return that number as is
If we get 3, we return 7
If we get 5, we return 6


This ensures that each valid number has exactly a 1/6 probability of being chosen, and we only make one random function call per pick.

# Complexity
- Time complexity:
$O(n)$

- Space complexity:
$O(n)$

# Code
```python3 []
class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        # Idea: map blacklisted elements withing the valid range i.e.
        # [0, n-len(blacklist)) to outside white (= !black) numbers. 
        # Then sample integers from [0, n-len(blacklist))
        self.n = n 
        self.n_valid = n - len(blacklist)
        self.mapping = {}

        blacklist = set(blacklist)
        outside_and_white = n-1

        for black in blacklist:
            if black < self.n_valid:
                while outside_and_white in blacklist:
                    outside_and_white -= 1

                self.mapping[black] = outside_and_white
                outside_and_white -= 1

    def pick(self) -> int:
        idx = random.randint(0, self.n_valid-1)
        return self.mapping.get(idx, idx)
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()
```
['Hash Table', 'Randomized', 'Python3']