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 where maxAvailable 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.