Python 4 lines O(BlogB)/ O(logB)
\ndef __init__(self, N: int, blacklist: List[int]):\n\tself.blacklist = [-1] + sorted(blacklist) + [N]\n\tself.cum_weights = list(itertools.accumulate(j - i - 1
```\ndef __init__(self, N: int, blacklist: List[int]):\n\tself.blacklist = [-1] + sorted(blacklist) + [N]\n\tself.cum_weights = list(itertools.accumulate(j - i - 1 for i, j in zip(self.blacklist, self.blacklist[1:])))\n\n\ndef pick(self) -> int:\n\tidx = random.choices(range(len(self.cum_weights)), cum_weights=self.cum_weights)[0]\n\treturn self.blacklist[idx] + random.randint(1, self.cum_weights[0] if idx == 0 else self.cum_weights[idx] - self.cum_weights[idx - 1])\n```\n\nMy goal is to reduce this problem to https://leetcode.com/problems/random-pick-with-weight/. I split [0,N) into partitions, where partition p_i has weight size(p_i). For random.choices to work quickly, I need to accumulate these values (if instead I did something like `random.choices(..., weights=self.weights)` behind the scenes `random.choices` would make the accumulated array anyway). This has complexity O(BlogB) as I need to sort the blacklist to get the sizes of the partitions.\n\nNext, I use `random.choices` to pick a random partition weighted by the sizes of the partition, and then pick a random number in that partition and add it to the blacklisted number before the partition. This has complexity O(logB) as there are O(B) partitions that `random.choices` has to do binary search on.
[]