Random Pick With Blacklist - Leetcode Solution

Problem Statement:

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,0,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]

Solution:

We will follow the following steps to solve this problem:

1. Create a hash set to store the list of blacklisted numbers.

2. Calculate the number of allowed numbers by subtracting the length of the blacklist from the total number range N.

3. Create a map to map the blacklisted numbers to their corresponding values in the allowed range.

4. For each blacklisted number, map it to its corresponding value in the allowed range.

5. Select a random number in the allowed range.

6. If the selected number is in the map, return the corresponding blacklisted number.

7. Otherwise, return the selected number.

Here is the Python code for the solution:

import random

class Solution:

def __init__(self, N: int, blacklist: List[int]):
    self.numeric_range = set(range(N))
    self.blacklist = set(blacklist)
    self.allowed = list(self.numeric_range - self.blacklist)
    self.mapping = {}
    
    # Map blacklisted numbers to their corresponding values in the allowed range
    map_index = 0 
    for blacklisted_number in sorted(self.blacklist):
        if map_index >= len(self.allowed):
            break
        
        while self.allowed[map_index] in self.mapping.values():
            map_index += 1
        
        self.mapping[blacklisted_number] = self.allowed[map_index]
        map_index += 1
    
def pick(self) -> int:
    """
    :rtype: int
    """
    rand = random.randint(0, len(self.allowed) - 1)
    if rand in self.mapping:
        return self.mapping[rand]
    else:
        return self.allowed[rand]

Time Complexity:

The time complexity of init() is O(nlogn) due to the sorting of the blacklisted numbers. The time complexity of pick() is O(1) on average as it just selects a random number from the allowed range and performs a map lookup.

1