710. Random Pick with Blacklist

Link

Solution

Basic idea is to remap the blacklist element. and also adjust the candidate range accordingly.

Suppose N=10, blacklist=[3, 5, 8, 9], re-map 3 and 5 to 7 and 6.

Redline is the new range of candidates.

     int M = 0;
    Map<Integer, Integer> map;
    Random random;
    public Solution(int N, int[] blacklist) {
        M = N - blacklist.length;
        map = new HashMap<>();
        for(int black : blacklist){
            map.put(black, -1);
        }
        N--; //N is not in the candidate list
        for(int black : blacklist){
            if(black < M){
                while(map.containsKey(N)) N--;
                map.put(black, N);
                N--;
            }
        }
        random = new Random();
        
    }
    
    public int pick() {
        int r = random.nextInt(M);
        if(map.containsKey(r)){
            return map.get(r);
        }
        return r;
    }