{x}
blog image

Random Pick with Blacklist

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 integer n and the blacklisted integers blacklist.
  • int pick() Returns a random integer in the range [0, n - 1] and not in blacklist.

 

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 <= 109
  • 0 <= blacklist.length <= min(105, n - 1)
  • 0 <= blacklist[i] < n
  • All the values of blacklist are unique.
  • At most 2 * 104 calls will be made to pick.

Solution Explanation:

This problem requires designing a data structure that allows efficient random selection from a range of integers, excluding a blacklist. A naive approach would involve repeatedly generating random numbers until a valid one is found, but this is inefficient, especially when the blacklist is large. The optimal solution uses a mapping to achieve O(1) pick time.

Algorithm:

  1. Initialization (__init__ / Constructor):

    • Calculate k, the number of valid integers (total numbers - blacklist size). This represents the size of our allowed range.
    • Create a dictionary/hash map (d) to store the mapping. This map will translate indices from the range [0, k-1] to valid integers from [0, n-1]
    • Iterate through the blacklist:
      • If a blacklisted number b is less than k (meaning it falls within the range we want to map), find a replacement.
      • We start the replacement search from k and iterate up (i). We find the first number i not present in the blacklist.
      • We map b to i in the dictionary (d[b] = i) and increment i.

  2. Pick (pick):

    • Generate a random integer x in the range [0, k-1].
    • If x is a key in d, return its mapped value (d[x]). Otherwise (it wasn't originally in the blacklist and thus hasn't been mapped), return x itself.

Time Complexity:

  • Initialization: O(m), where m is the length of the blacklist. We iterate through the blacklist once and the while loop to find a valid replacement in the worst-case runs m times.
  • Pick: O(1). Lookup in a hash map (dictionary) takes constant time on average.

Space Complexity:

  • O(m), where m is the length of the blacklist. The extra space is used to store the mapping dictionary/hash map. In the worst case where all blacklisted numbers are less than k, the map will have m entries.

Code Explanation (Python):

The Python code directly implements this algorithm. randrange(self.k) generates a random integer in the desired range. The get(x,x) handles the mapping; if x is in the dictionary, its mapped value is returned; otherwise, x itself is returned.

Code Explanation (Java, C++, Go):

The Java, C++, and Go codes follow the same algorithmic approach. They use HashMap, unordered_map, and map respectively to achieve the mapping. The getOrDefault function in Java, and the ternary operator in C++ provide efficient handling of the mapping. Go uses a similar approach. The core logic is identical across all languages. The choice of the hash map data structure ensures the O(1) average time complexity for the pick operation.

Example Walkthrough:

Let's say n = 7 and blacklist = [2, 3, 5].

  1. Initialization:

    • k = 7 - 3 = 4
    • d will be a mapping from [0, 3] to valid numbers in [0, 6].
    • We iterate:
      • b = 2: i starts at 4. 4 is not in blacklist, so d[2] = 4. i becomes 5.
      • b = 3: i is 5. 5 is in blacklist. i becomes 6. 6 is not in blacklist, so d[3] = 6. i becomes 7.
      • b = 5: 5 >= k, so it's ignored.
    • d becomes {2: 4, 3: 6}.

  2. Pick:

    • Suppose rand.nextInt(4) returns 1. 1 is not in d, so 1 is returned.
    • Suppose rand.nextInt(4) returns 2. 2 is in d, so d[2] = 4 is returned.

This ensures a uniform distribution of numbers from the allowed range while effectively handling the blacklist.