LeetCode 710. Random Pick with Blacklist

Linear Search | Binary Search | HashMap

Given a blacklist B containing unique integers from [0, N), write a function to return a uniform random integer from [0, N) which is NOT in B.

Optimize it such that it minimizes the call to system’s Math.random().

Note:

1. 1 <= N <= 1000000000

2. 0 <= B.length < min(100000, N)

3. [0, N) does NOT include N. See interval notation.

Example 1:

Input: 
["Solution","pick","pick","pick"]
[[1,[]],[],[],[]]
Output: [null,0,0,0]

Example 2:

Input: 
["Solution","pick","pick","pick"]
[[2,[]],[],[],[]]
Output: [null,1,1,1]

Example 3:

Input: 
["Solution","pick","pick","pick"]
[[3,[1]],[],[],[]]
Output: [null,0,0,2]

Example 4:

Input: 
["Solution","pick","pick","pick"]
[[4,[2]],[],[],[]]
Output: [null,1,3,1]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, N and the blacklist B. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Solution

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

// Solution 1: Binary Search. O(log)
class Solution {
    vector<int> v;
    std::random_device rd;
    int mod;
public:
    Solution(int N, vector<int> blacklist) {
        mod = N - blacklist.size();
        sort(blacklist.begin(), blacklist.end());
        v = blacklist;
        v.push_back(N);
        for (int i = 0; i < v.size(); i++) v[i] -= i;
    }
    
    int pick() {
        int index = rd() % mod;
        auto it = upper_bound(v.begin(), v.end(), index);
        return index + (it - v.begin());
    }
};

// Solution 2: hash_map; O(1)
class Solution {
    random_device rd;
    unordered_map<int, int> updated_index;
    int mod;
public:
    Solution(int N, vector<int>& blacklist) {
        mod = N - blacklist.size();
        set<int> blacklist_set(blacklist.begin(), blacklist.end());
        
        int swap_num = N - 1;
        for (int blacklist_element : blacklist_set) {
            if (blacklist_element >= mod) break;
            while (blacklist_set.count(swap_num) > 0) {
                swap_num--;
            }
            updated_index[blacklist_element] = swap_num;
            swap_num--;
        }
    }
    
    int pick() {
        int index = rd() % mod;
        if (updated_index.count(index) > 0) {
            return updated_index[index];
        }
        return index;
    }
};