Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/710.html

710. Random Pick with Blacklist

Level

Hard

Description

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

Given an integer N and a blacklist B, there are N - B.length numbers that can be selected. For example, if N is 100 and B.length is 10, then there are 100 - 10 = 90 numbers that can be selected. Therefore, call Math.random() so that the returned integer is in the range [0, N - B.length).

For each number in the blacklist, it is either less than N - B.length or greater than or equal to N - B.length. If a number in the blacklist is less than N - B.length, then it should be mapped to a number in the range [N - B.length, N) which is not in the blacklist.

In the class, maintain size which is the number of integers that can be selected, maintain a set to store the numbers in the blacklist, and maintain a map.

For the constructor, initialize size = N - B.length, and add all the numbers in the blacklist to the set. Then for each number in the blacklist, map it to num which is in the range [size, N) and is not in the blacklist (num is updated after each mapping), with the map updated.

For the method pick, randomly select an integer in the range [0, size), get the corresponding integer from the map (if the integer is not in the map, then the integer remains unchanged), and return the integer.

  • class Solution {
        int size;
        Set<Integer> blacklistSet;
        Map<Integer, Integer> map;
    
        public Solution(int N, int[] blacklist) {
            size = N - blacklist.length;
            blacklistSet = new HashSet<Integer>();
            for (int blacklistNum : blacklist)
                blacklistSet.add(blacklistNum);
            map = new HashMap<Integer, Integer>();
            int num = size;
            for (int blacklistNum : blacklist) {
                if (blacklistNum < size) {
                    while (blacklistSet.contains(num))
                        num++;
                    map.put(blacklistNum, num);
                    num++;
                }
            }
        }
        
        public int pick() {
            int num = (int) (Math.random() * size);
            num = map.getOrDefault(num, num);
            return num;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(N, blacklist);
     * int param_1 = obj.pick();
     */
    
  • // OJ: https://leetcode.com/problems/random-pick-with-blacklist/
    // Time:
    //      Solution: O(BlogB)
    //      pick: O(1)
    // Space: O(B)
    class Solution {
        unordered_map<int, int> m;
        int len;
    public:
        Solution(int n, vector<int>& B) {
            len = n - B.size();
            sort(begin(B), end(B));
            int j = lower_bound(begin(B), end(B), len) - begin(B), N = B.size(), next = len;
            for (int i = 0; i < N && B[i] < len; ++i) {
                while (j < N && B[j] == next) ++j, ++next;
                m[B[i]] = next++;
            }
        }
        int pick() {
            int r = rand() % len;
            return m.count(r) ? m[r] : r;
        }
    };
    
  • class Solution:
        def __init__(self, n: int, blacklist: List[int]):
            self.k = n - len(blacklist)
            self.d = {}
            i = self.k
            black = set(blacklist)
            for b in blacklist:
                if b < self.k:
                    while i in black:
                        i += 1
                    self.d[b] = i
                    i += 1
    
        def pick(self) -> int:
            x = randrange(self.k)
            return self.d.get(x, x)
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(n, blacklist)
    # param_1 = obj.pick()
    
    
    
  • 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();
     */
    

All Problems

All Solutions