Random Pick with Blacklist solution and explanation
Google
9 more videos on this problem
Random Pick with blacklist || LeetcodePepcoding · 21:10 · 3K views
LeetCode 710. Random Pick with Blacklist | Two Sigma Interview Problem宰相小甘罗 · 12:10 · 1K views
【每日一题】710. Random Pick with Blacklist, 11/14/2019Huifeng Guan · 55:56 · 666 views
LeetCode 710. Random Pick with Blacklist 中文 | Two Sigma面试题宰相小甘罗 · 10:35 · 493 views
Leetcode 710. Random Pick with Blacklist | C++Unofficial Sendoh · 10:13 · 378 views
LeetCode 710 | Random Pick with Blacklist | HashMap | Random | JavaSleepy Cracker · 6:47 · 192 views
710. Random Pick with Blacklist [12/30/20 - 1/5]KG修罗场 · 16:08 · 42 views
Leetcode 0710. Random Pick with BlacklistFearless Learner · 9:58 · 32 views
LeetCode 710: Random Pick with BlacklistAlitaCode · 29:02 · 29 views
No Sound Leetcode 710: Random Pick with BlacklistExtremeProgrammer · 1:40 · 11 views
The problem
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 integernand the blacklisted integersblacklist.int pick()Returns a random integer in the range[0, n - 1]and not inblacklist.
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
Constraints:
1 <= n <= 1090 <= blacklist.length <= min(105, n - 1)0 <= blacklist[i] < n- All the values of
blacklistare unique. - At most
2 * 104calls will be made topick.
Approach overview
Problem Overview: You need to randomly return an integer from the range [0, n) while excluding numbers listed in a blacklist. Every valid number must have equal probability. The challenge is avoiding blacklisted values without repeatedly generating random numbers and rejecting them.
Approach 1: Binary Search on Sorted Blacklist (Pick: O(log b), Preprocess: O(b log b))
Sort the blacklist first. Instead of picking from [0, n), pick a random index k from the range [0, n - b) where b is the blacklist size. This represents the index of the k-th valid number if the blacklist didn’t exist. Use binary search on the sorted blacklist to determine how many blacklisted numbers are less than or equal to the candidate value and shift the result accordingly. The key insight: each blacklisted value "pushes" valid numbers forward. Binary search efficiently finds how many pushes occur. Sorting dominates preprocessing at O(b log b), and each random pick costs O(log b). Space complexity is O(b). This approach relies on binary search and works well when the blacklist is static.
Approach 2: Hash Map with Remapping (Pick: O(1), Preprocess: O(b))
The optimal solution remaps blacklisted values that fall inside the valid picking range. Let m = n - b. Generate random numbers only from [0, m). If a blacklisted number appears inside this range, map it to a safe number from the upper range [m, n) that is not blacklisted. Build a hash map where each blocked value in the lower range points to a valid replacement. During pick(), generate a random integer x in [0, m). If x exists in the map, return the mapped value; otherwise return x. Preprocessing scans the blacklist and uses a set or map for constant-time checks, resulting in O(b) time and space. Each random pick runs in O(1). This method heavily uses hash tables and randomized selection concepts from randomized algorithms. It guarantees uniform distribution across valid numbers.
Recommended for interviews: The hash map remapping approach is what most interviewers expect because it achieves O(1) pick time while keeping preprocessing linear. Explaining the binary search idea first shows you understand the indexing trick of skipping blacklisted values. Implementing the remapping solution demonstrates strong command of array indexing, hashing, and probability correctness.
Approach 1: Binary Search on Sorted Blacklist
This approach involves preprocessing the blacklist by sorting it. Upon calling 'pick', we randomly select a number from 0 to n - blacklist.length - 1 and adjust it using binary search to account for blacklisted numbers.
import random
from bisect import bisect_left
class Solution:
def __init__(self, n: int, blacklist: list):
self.n = n
self.blacklist = sorted(blacklist)
self.total_possible = n - len(blacklist)
def pick(self) -> int:
rand_index = random.randint(0, self.total_possible - 1)
insert_point = bisect_left(self.blacklist, rand_index)
return rand_index + insert_pointimport java.util.*;
class Solution {
private int n;
private int[] blacklist;
private Random rand;
public Solution(int n, int[] blacklist) {
Arrays.sort(blacklist);
this.n = n;
this.blacklist = blacklist;
this.rand = new Random();
}
public int pick() {
int randIndex = rand.nextInt(n - blacklist.length);
int low = 0, high = blacklist.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (blacklist[mid] - mid > randIndex)
high = mid;
else
low = mid + 1;
}
return randIndex + low;
}
}In this Python solution, the 'bisect_left' function is used to find the number of blacklisted numbers less than the current random number, thus adjusting it directly to a safe number.
Time Complexity: O(log B) per pick call, where B is the length of blacklist.
Space Complexity: O(B) due to storage of the blacklist.
Approach 2: Hash Map with Mapping
This approach involves creating a mapping from blacklisted numbers under n-k (where k is the list length) to valid un-blacklisted numbers above that range. This method efficiently handles cases when n is large but the blacklist is relatively small.
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>
using namespace std;
class Solution {
private:
unordered_map<int, int> mapping;
int possibleCount;
public:
Solution(int n, vector<int>& blacklist) {
int bSize = blacklist.size();
possibleCount = n - bSize;
unordered_set<int> blacklistSet(blacklist.begin(), blacklist.end());
int last = n - 1;
for (int b : blacklist) {
if (b < possibleCount) {
while (blacklistSet.count(last)) {
last--;
}
mapping[b] = last;
last--;
}
}
}
int pick() {
int randIndex = rand() % possibleCount;
return mapping.count(randIndex) ? mapping[randIndex] : randIndex;
}
};class Solution {
constructor(n, blacklist) {
this.map = {};
this.bound = n - blacklist.length;
const blacklistSet = new Set(blacklist);
let last = n - 1;
for (const b of blacklist) {
if (b < this.bound) {
while (blacklistSet.has(last)) {
last--;
}
this.map[b] = last;
last--;
}
}
}
pick() {
const rand = Math.floor(Math.random() * this.bound);
return this.map[rand] !== undefined ? this.map[rand] : rand;
}
}This C++ solution sets up the mapping from blacklisted to valid indices during initialization. The 'pick' method then efficiently selects and returns a valid random number using the precomputed map.
Time Complexity: O(1) per pick call.
Space Complexity: O(B) due to the hash map storage requirement.
Approach 3: Default Approach
type Solution struct {
d map[int]int
k int
}
func Constructor(n int, blacklist []int) Solution {
k := n - len(blacklist)
i := k
black := map[int]bool{}
for _, b := range blacklist {
black[b] = true
}
d := map[int]int{}
for _, b := range blacklist {
if b < k {
for black[i] {
i++
}
d[b] = i
i++
}
}
return Solution{d, k}
}
func (this *Solution) Pick() int {
x := rand.Intn(this.k)
if v, ok := this.d[x]; ok {
return v
}
return x
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(n, blacklist);
* param_1 := obj.Pick();
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search on Sorted Blacklist | Time Complexity: O(log B) per pick call, where B is the length of blacklist. |
| Hash Map with Mapping | Time Complexity: O(1) per pick call. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Sorted Blacklist | Preprocess: O(b log b), Pick: O(log b) | O(b) | When the blacklist is static and binary search logic is acceptable for each pick |
| Hash Map with Remapping | Preprocess: O(b), Pick: O(1) | O(b) | Best general solution when frequent random picks are required |
Frequently asked questions
Is Random Pick with Blacklist easy or hard?
Random Pick with Blacklist is classified as a Hard problem on LeetCode. The difficulty comes from designing a constant-time random picker while preserving uniform probability across all valid numbers.
How to solve Random Pick with Blacklist in O(n)?
Use a remapping technique with a hash map. Compute m = n - blacklist.size() and only generate random numbers in [0, m). Any blacklisted number inside this range is mapped to a valid number in [m, n). Building this mapping requires O(b) time and space.
What is the best approach for Random Pick with Blacklist?
The hash map remapping approach is the optimal solution. It preprocesses the blacklist in O(b) time and ensures each call to pick() runs in O(1). Blacklisted numbers in the lower selection range are mapped to valid numbers in the upper range, guaranteeing uniform randomness.
What data structure is used in Random Pick with Blacklist?
The optimal solution uses a hash map and a hash set. The set tracks blacklisted values, while the map remaps blocked indices in the lower range to valid numbers in the upper range. Some alternative implementations also use sorted arrays with binary search.
What is the time complexity of Random Pick with Blacklist?
The optimal hash map solution runs preprocessing in O(b) time and space, where b is the blacklist size, and each pick() call runs in O(1). A binary search alternative requires O(b log b) preprocessing and O(log b) time per random pick.
Random Pick with Blacklist Python or Java solution approach
Both Python and Java implementations follow the same logic. Precompute m = n - blacklist.length, map invalid indices in [0, m) to valid values in [m, n), and during pick() generate a random integer in [0, m). Return the mapped value if it exists, otherwise return the random number.
Is Random Pick with Blacklist asked at Google, Amazon, or Meta?
Randomized data structure problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests hash map usage, probability correctness, and efficient preprocessing for repeated queries.