Java O(1) time / O(B) space, Blacklist remapping
This solution generates numbers uniformly with probality 1/(N-B) with single call to Math.random().\n\nA random number 0 <=k < N-B is generated using Math.rando
This solution generates numbers uniformly with probality 1/(N-B) with single call to Math.random().\n\nA random number 0 <=k < N-B is generated using Math.random * (N-B) can contain blacklisted numbers. In that case, those blacklisted numbers will be mapped to numbers from N-B to N-1. Note that numbers form N-B to N can contain blacklisted numbers and those should be skipped.\n\nNote that doing binary search in constructor is faster than using a map because of cache locality of arrays\n\n\n```\nclass Solution {\n    int[] blackList;\n    int length;\n    Map<Integer, Integer> blackListMapping = new HashMap<>();\n\n    public Solution(int N, int[] blacklist) {\n        Arrays.sort(blacklist);\n        this.blackList = blacklist;\n        this.length = N-blacklist.length;\n\n        for(int i = 0, j=this.length; i<blacklist.length && blacklist[i] < this.length && j <N;) {\n            if(Arrays.binarySearch(blacklist, j) >=0) {\n                j++;\n                continue;\n            }\n            blackListMapping.put(blacklist[i++],j++);\n        }\n    }\n\n    public int pick() {\n        int idx = (int) (Math.random() * length);\n        if(blackListMapping.containsKey(idx)) return blackListMapping.get(idx);\n        return idx;\n    }\n}\n```\n
[]