Last updated on March 2nd, 2025 at 02:47 pm

Here, we see a Random Pick with Blacklist LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

String

Level of Question

Hard

Random Pick with Blacklist LeetCode Solution

1. 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

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Hash Mapping with Remapping”. The code uses hash maps to remap blacklisted indices to valid indices in a range, ensuring efficient random selection from a valid subset of numbers.

3. Code Implementation in Different Languages

3.1 Random Pick with Blacklist 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;
    }
};

3.2 Random Pick with Blacklist 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.3 Random Pick with Blacklist 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;
};

3.4 Random Pick with Blacklist 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)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(1)	O(b)
Java	O(1)	O(b)
JavaScript	O(1)	O(b)
Python	O(1)	O(b)

where B is the size of the blacklist (blacklist.size() or len(blacklist)).

• The code is efficient for both initialization and random picking.
• The use of hash maps ensures constant-time lookups and remapping.
• The approach avoids iterating over the blacklist during each random pick, making the pick function very fast (O(1)).