Last updated on October 9th, 2024 at 06:21 pm

Here, We see Random Pick with Blacklist LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Random Pick with Blacklist LeetCode Solution

Problem Statement

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

1. Random Pick with Blacklist LeetCode Solution C++

class Solution {
public:
    int idx;
    unordered_map<int, int>mp;
    set<int> s;
    Solution(int n, vector<int>& blacklist) {
       idx = n - blacklist.size();
       n--;
       for(int i = 0; i<blacklist.size(); i++) s.insert(blacklist[i]);
       for(int i = 0; i<blacklist.size(); i++){
           if(blacklist[i] < idx){
           while(s.find(n) != s.end())n--;
           mp[blacklist[i]] = n;
           n--; 
           }
       } 
    }
    
    int pick() {
      int ans = rand()%(idx);
      if(mp.count(ans)) return mp[ans];
      return ans;
    }
};

2. Random Pick with Blacklist LeetCode Solution Java

class Solution {
    Map<Integer, Integer> map;
    Random rand = new Random();
    int size;

    public Solution(int n, int[] blacklist) {
        map = new HashMap<>();
        size = n - blacklist.length;
        int last = n - 1;
        for (int b: blacklist) {
            map.put(b, -1);
        }
        for (int b: blacklist) {
            if (b >= size) {
                continue;
            }
            while (map.containsKey(last)) {
                last--;
            }
            map.put(b, last);
            last--;
        }
    }
    public int pick() {
        int idx = rand.nextInt(size);
        if (map.containsKey(idx)) {
            return map.get(idx);
        }
        return idx;
    }
}

3. Random Pick with Blacklist LeetCode Solution JavaScript

var Solution = function(n, blacklist) {
    this.space = n - blacklist.length;
    this.map = {};

    blacklist.forEach((b, i) => {
        const next = this.space + i;

        const head = this.map[b] === undefined ? b : this.map[b];
        const tail = this.map[next] === undefined ? next : this.map[next];

        this.map[head] = tail;
        this.map[tail] = head;
    });
};

Solution.prototype.pick = function() {
    const result = Math.floor(Math.random() * this.space);
    return this.map[result] || result;
};

4. Random Pick with Blacklist LeetCode Solution Python

class Solution(object):

    def __init__(self, n, blacklist):
        self.hashmap={}
        for b in blacklist:
            self.hashmap[b]=-1
        self.length=n-len(blacklist)
        flag=n-1
        for b in blacklist:
            if b<self.length: 
                while flag in self.hashmap:
                    flag-=1
                self.hashmap[b]=flag
                flag-=1
            
    def pick(self):
        seed=random.randrange(self.length)
        return self.hashmap.get(seed,seed)