The Random Pick with Blacklist problem asks you to implement a data structure that allows for efficiently picking a random integer from the range [0, n), excluding any integers present in a given blacklist array. Every valid integer (not in the blacklist) should have an equal probability of being picked.
n and a list blacklist of unique integers in the range [0, n).__init__(n, blacklist): Constructor that initializes the data structure.pick(): Returns a random integer in [0, n) not in the blacklist. Each valid integer must have the same probability of being returned.1 <= n <= 10^90 <= blacklist.length < min(10^5, n - 1)0 <= blacklist[i] < npick() should run in O(1) time.
At first, you might consider generating random numbers in [0, n) and retrying if the number is in the blacklist. However, this approach is inefficient if the blacklist is large, since you could waste a lot of time retrying.
Next, you might think about precomputing a list of all valid numbers (those not in the blacklist) and picking randomly from it. But since n can be as large as 10^9, this would use too much memory.
The optimized approach is to remap the blacklist values that fall in the range of possible picks to valid numbers outside that range. This way, you can pick a random number in a compact range and, if needed, translate it to a valid number. This leverages the fact that the number of blacklisted items is much smaller than n.
Let's break down the optimized solution step by step:
len(blacklist) numbers to exclude, there are valid_range = n - len(blacklist) valid numbers. We can pick a random integer x in [0, valid_range).
[0, valid_range) may be blacklisted. We must avoid picking them directly.
b in [0, valid_range), we map it to a valid number in [valid_range, n) that is not blacklisted. We store these mappings in a hash map for O(1) lookups.
x in [0, valid_range).x is not blacklisted, return x.x is blacklisted, return its mapped value from the hash map.pick() operation O(1).
This approach is memory efficient and scales well even for large n.
Example:
n = 7, blacklist = [2, 3, 5]
valid_range = 7 - 3 = 4. We'll pick random numbers in [0, 4), i.e., 0, 1, 2, 3.
2, 3 are in [0, 4) and must be remapped.
[4, 7) are 4, 5, 6. 5 is blacklisted, so valid targets are 4 and 6.
Thus, the possible results are 0, 1, 4, 6, all equally likely.
pick() operation due to hash map lookup.
The optimized approach is highly efficient and suitable for large n and moderate blacklist sizes.
The Random Pick with Blacklist problem demonstrates how clever remapping and hash maps can transform an inefficient brute-force solution into an optimal one. By reducing the random pick space and only remapping the necessary blacklisted numbers, we achieve O(1) random picks with minimal space overhead. This strategy is elegant because it leverages both mathematical insight and efficient data structures to solve a problem that at first seems daunting for large inputs.
import random
class Solution:
def __init__(self, n: int, blacklist: list[int]):
self.n = n
self.blacklist = set(blacklist)
self.bound = n - len(blacklist)
self.mapping = {}
black_in_range = set(b for b in blacklist if b < self.bound)
white_out_range = set(range(self.bound, n)) - self.blacklist
white_iter = iter(white_out_range)
for b in black_in_range:
self.mapping[b] = next(white_iter)
def pick(self) -> int:
x = random.randint(0, self.bound - 1)
return self.mapping.get(x, x)
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <random>
class Solution {
int bound;
std::unordered_map<int, int> mapping;
std::mt19937 gen;
std::uniform_int_distribution<> dist;
public:
Solution(int n, std::vector<int>& blacklist) {
int B = blacklist.size();
bound = n - B;
std::unordered_set<int> black(blacklist.begin(), blacklist.end());
std::unordered_set<int> black_in_range;
for (int b : blacklist) {
if (b < bound) black_in_range.insert(b);
}
std::unordered_set<int> white_out_range;
for (int i = bound; i < n; ++i) {
if (!black.count(i))
white_out_range.insert(i);
}
auto it = white_out_range.begin();
for (int b : black_in_range) {
mapping[b] = *it;
++it;
}
std::random_device rd;
gen = std::mt19937(rd());
dist = std::uniform_int_distribution<>(0, bound - 1);
}
int pick() {
int x = dist(gen);
if (mapping.count(x)) return mapping[x];
return x;
}
};
import java.util.*;
class Solution {
private int bound;
private Map<Integer, Integer> mapping;
private Random rand;
public Solution(int n, int[] blacklist) {
int B = blacklist.length;
bound = n - B;
mapping = new HashMap<>();
Set<Integer> black = new HashSet<>();
for (int b : blacklist) black.add(b);
Set<Integer> blackInRange = new HashSet<>();
for (int b : blacklist) {
if (b < bound) blackInRange.add(b);
}
Set<Integer> whiteOutRange = new HashSet<>();
for (int i = bound; i < n; i++) {
if (!black.contains(i)) whiteOutRange.add(i);
}
Iterator<Integer> it = whiteOutRange.iterator();
for (int b : blackInRange) {
mapping.put(b, it.next());
}
rand = new Random();
}
public int pick() {
int x = rand.nextInt(bound);
return mapping.getOrDefault(x, x);
}
}
var Solution = function(n, blacklist) {
this.bound = n - blacklist.length;
this.mapping = new Map();
let blackSet = new Set(blacklist);
let blackInRange = new Set();
for (let b of blacklist) {
if (b < this.bound) blackInRange.add(b);
}
let whiteOutRange = [];
for (let i = this.bound; i < n; ++i) {
if (!blackSet.has(i)) whiteOutRange.push(i);
}
let idx = 0;
for (let b of blackInRange) {
this.mapping.set(b, whiteOutRange[idx++]);
}
};
Solution.prototype.pick = function() {
let x = Math.floor(Math.random() * this.bound);
return this.mapping.has(x) ? this.mapping.get(x) : x;
};