# Random Pick with Blacklist LeetCode Solution

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

## 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

## 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;
}
};```Code language: JavaScript (javascript)```

## 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;
}
}```Code language: PHP (php)```

## 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];

});
};

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

## 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)```Code language: HTML, XML (xml)```
Scroll to Top