Random Pick with Blacklist — LeetCode 710 Python Solution

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.

Example

Input

["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]

Output

[null, 0, 4, 1, 6, 1, 0, 4]

Explanation

Solution solution = new Solution(7, [2, 3, 5]);

Python solution

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()

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 710. Random Pick with Blacklist is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems