Leetcode 710. Random Pick with Blacklist
Problem Explanation
This problem requires generating random numbers within a given range, while excluding a list of 'blacklist' values. The challenge has two parts - the Solution
method sets up the problem by creating a map that excludes blacklisted numbers and the pick
method generates a random value which is not blacklisted.
Example Walk-through
Let's assume N
= 4 and the blacklist (B
) is [2]:
map
would initially be set to {2: -1} to mark the blacklisted number.- Then for
b
in the blacklist,map[b] = maxAvailable
is performed wheremaxAvailable
is the non-blacklisted maximum number. - So, essentially
map
transforms to {2: 3}.
When pick()
is called, it generates a random number num
in the range validRange
(which is 4-1=3 in our example). If num
happens to be a blacklisted number, it would find that number in the map
and returns the maxAvailable
number else it will directly return num
.
Python Solution
1 2python 3import random 4 5class Solution: 6 def __init__(self, n, blacklist): 7 self.n = n 8 self.maxRange = n - len(blacklist) 9 self.mapping = {} 10 blacklistSet = set(blacklist) 11 12 # If blacklisted number in valid range, 13 # map it to farthest available number not present in blacklist 14 for b in blacklist: 15 if b < self.maxRange: 16 while self.n - 1 in blacklistSet: 17 self.n -= 1 18 self.mapping[b] = self.n - 1 19 20 def pick(self): 21 num = random.randrange(self.maxRange) 22 if num in self.mapping: 23 return self.mapping[num] 24 else: 25 return num
Java Solution
1
2java
3class Solution {
4 int maxRange;
5 Map<Integer, Integer> map;
6 Random rand = new Random();
7
8 public Solution(int n, int[] blacklist) {
9 this.map = new HashMap<>();
10 this.maxRange = n - blacklist.length;
11 Set<Integer> blacklistSet = new HashSet<>();
12 for (int b : blacklist) {
13 blacklistSet.add(b);
14 }
15
16 for (int b : blacklist) {
17 if (b < maxRange) {
18 while (blacklistSet.contains(n - 1)) {
19 n--;
20 }
21 map.put(b, n - 1);
22 }
23 }
24 }
25
26 public int pick() {
27 int num = rand.nextInt(maxRange);
28 return map.getOrDefault(num, num);
29 }
30}
JavaScript Solution
1
2javascript
3class Solution {
4 constructor(n, blacklist) {
5 this.maxRange = n - blacklist.length;
6 this.map = new Map();
7 let blacklistSet = new Set(blacklist);
8 for (let b of blacklist) {
9 if (b < this.maxRange) {
10 while (blacklistSet.has(n - 1)) {
11 n--;
12 }
13 this.map.set(b, n - 1);
14 }
15 }
16 }
17
18 pick() {
19 let num = Math.floor(Math.random() * this.maxRange);
20 if (this.map.has(num)) {
21 return this.map.get(num);
22 } else {
23 return num;
24 }
25 }
26}
C++ Solution
1
2cpp
3class Solution {
4private:
5 int maxRange;
6 unordered_map<int, int> map;
7public:
8 Solution(int n, vector<int>& blacklist) {
9 this->maxRange = n - blacklist.size();
10 unordered_set<int> blacklistSet(blacklist.begin(), blacklist.end());
11
12 for (int b : blacklist) {
13 if (b < this->maxRange) {
14 while (blacklistSet.count(n - 1)) {
15 n--;
16 }
17 this->map[b] = n - 1;
18 }
19 }
20 }
21
22 int pick() {
23 int num = rand() % this->maxRange;
24 return this->map.count(num) ? this->map[num] : num;
25 }
26};
C# Solution
1
2csharp
3public class Solution {
4 int maxRange;
5 Dictionary<int, int> map;
6 Random random = new Random();
7
8 public Solution(int n, int[] blacklist) {
9 this.map = new Dictionary<int, int>();
10 this.maxRange = n - blacklist.Length;
11 HashSet<int> blacklistSet = new HashSet<int>(blacklist);
12
13 foreach (int b in blacklist) {
14 if (b < maxRange) {
15 while (blacklistSet.Contains(n - 1)) {
16 n--;
17 }
18 map[b] = n - 1;
19 }
20 }
21 }
22
23 public int Pick() {
24 int num = random.Next(maxRange);
25 return map.ContainsKey(num) ? map[num] : num;
26 }
27}
In all the implementations, random numbers not present in blacklist can be generated with minimal calls to random number generator. For the blacklisted numbers, we map them to the farthest non-blacklist number available. Whenever the number is picked, if it's a key of the map, we return the mapped value else return the number itself directly.## Ruby Solution
Ruby solution can be formulated using its native features in the similar way as we did in python and java.
1
2ruby
3class Solution
4 def initialize(n, blacklist)
5 @maxRange = n - blacklist.length
6 @map = {}
7 blacklistSet = Set.new(blacklist)
8 blacklist.each do |b|
9 if b < @maxRange
10 while blacklistSet.include? n - 1
11 n -= 1
12 end
13 @map[b] = n - 1
14 end
15 end
16 end
17
18 def pick
19 num = rand(@maxRange)
20 if @map.has_key?(num)
21 return @map[num]
22 else
23 return num
24 end
25 end
26end
In this Ruby implementation, we used the Set
class that supports rapid member lookup and which is used to check whether the number to be mapped is blacklisted or not. The rand(n)
is upto but excluding n
in ruby hence is equivalent to random.randrange
in python.
Go Solution
The Go solution can be written similar to other solutions.
1
2go
3import "math/rand"
4
5type Solution struct {
6 maxRange int
7 mapping map[int]int
8}
9
10func Constructor(n int, blacklist []int) Solution {
11 maxRange := n - len(blacklist)
12 mapping := make(map[int]int)
13 blacklistSet := make(map[int]struct{})
14
15 for _, b := range blacklist {
16 blacklistSet[b] = struct{}{}
17 }
18
19 for _, b := range blacklist {
20 if b < maxRange {
21 for {
22 if _, ok := blacklistSet[n-1]; !ok {
23 break
24 }
25 n--
26 }
27 mapping[b] = n - 1
28 }
29 }
30
31 return Solution{maxRange, mapping}
32}
33
34
35func (this *Solution) Pick() int {
36 num := rand.Intn(this.maxRange)
37 if val, ok := this.mapping[num]; ok {
38 return val
39 }
40 return num
41}
This Go code uses the same strategy as the other versions. map[int]struct{}
is used as a Set substitute because Golang has no built-in Set data structure. The comma ok idiom is used to check if a value exists in the map or not.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.