Google - Random Pick with Blacklist

1. Thinking process

If you whitelist from first, it take O(N).

=> We only want to build a whitelist O(N - len(blacklist)).

So we build a whitelist size M = N - len(blacklist) => Random from [0, M), if the value blacklist < M => Map it to the value that > M but not in blacklist

=> Build a blacklist with size O(B).

2. Dry run code

import random

class Solution:
    def __init__(self, n: int, blacklist: list[int]):
        self.blackset = set(blacklist)
        self.m = n - len(blacklist)  # size of valid range
        self.mapping = {}

        # Step 1: build whitelist (numbers >= m that are not blacklisted)
        whitelist = [x for x in range(self.m, n) if x not in self.blackset]
        w_i = 0  # pointer to whitelist

        # Step 2: remap blacklisted numbers < m
        for b in blacklist:
            if b < self.m:
                self.mapping[b] = whitelist[w_i]
                w_i += 1

    def pick(self) -> int:
        x = random.randint(0, self.m - 1)
        # if x is blacklisted, map it to a valid number
        return self.mapping.get(x, x)

=> Time complexity: O(B) because you build whitelist from this.

Last Updated On October 23, 2025