Mapping to whitelisted, in O(1)
IntuitionMy first thought was to add all the whitelisted numbers (numbers not in the blacklist) to an ArrayList and then get random on indexes, but that would b
# Intuition
My first thought was to add all the whitelisted numbers (numbers not in the blacklist) to an ArrayList and then get random on indexes, but that would be in TC = O(N).
So then, I decided to map the numbers in the blacklist to other whitelisted numbers.

# Approach
So what we do now is, we first find the count of valid numbers (N - blacklist.length), this gives us the numbers we have to find random from. Now we add the blacklisted numbers into an hashmap and then blacklist[i] < valid count, we map it to a whitelisted number(we start the mapping from the end).
The pick method is simple, we just get random and check if the given val is not in blacklist and return it, otherwise we return the number mapped to our val.
# Complexity
- Time complexity:
The time complexity of this solution will be O(1).

- Space complexity:
Map space will be taken, which would at max be O(blacklist.length).
# Code
```java []
class Solution {
    int valid;
    HashMap<Integer, Integer> map;
    Random r;
    public Solution(int n, int[] blacklist) {
        map = new HashMap<>();
        r = new Random();
        for(int i=0; i<blacklist.length; i++){
            map.put(blacklist[i], -1);
        }
        valid = n - blacklist.length;
        for(int i = 0; i<blacklist.length; i++){
            if(blacklist[i] < valid){
                while(map.containsKey(n-1)) n--;
                map.put(blacklist[i], n-1);
                n--;
            }
        }
    }
    
    public int pick() {
        int val = r.nextInt(valid);
        if(map.containsKey(val)){
            return map.get(val);
        }else{
            return val;
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */
```
['Java']