We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Random Pick with Blacklist

Difficulty: Hard

Problem Description

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.

Key Insights

  • The range of possible integers is [0, n - 1].
  • We need to avoid integers present in the blacklist.
  • The number of integers to choose from may be significantly reduced by the blacklist.
  • Efficient random selection requires minimizing the number of calls to a built-in random function.

Space and Time Complexity

Time Complexity: O(1) for pick() after O(m log m) for preprocessing the blacklist, where m is the size of the blacklist.
Space Complexity: O(m) for storing the blacklist and the mapping of blacklisted integers.

Solution

To solve the problem, we can use a hash set to store the blacklisted integers for O(1) average time complexity lookups. We also create a mapping for the blacklisted integers to available integers that are not in the blacklist.

  1. Preprocessing: Store the blacklisted integers in a hash set for quick access. Determine how many integers are blacklisted and calculate how many valid integers remain.
  2. Random Selection: In the pick() function, randomly select an integer in the range [0, n - 1]. If the selected integer is in the blacklist, use the mapping to find a valid integer that is not blacklisted.

This approach ensures that all valid integers are equally likely to be chosen while keeping the implementation efficient.

Code Solutions

import random

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        self.n = n
        self.blacklisted = set(blacklist)
        self.blacklist_size = len(blacklist)

        # Map blacklisted integers to valid integers
        self.mapping = {}
        # The largest possible integer that can be picked
        last_valid = n - 1

        for b in blacklist:
            if b >= n - self.blacklist_size:
                while last_valid in self.blacklisted:
                    last_valid -= 1
                self.mapping[b] = last_valid
                last_valid -= 1

    def pick(self) -> int:
        # Get a random number in the range [0, n - 1]
        rand = random.randint(0, self.n - 1)
        # If it is blacklisted, return the mapped value
        return self.mapping.get(rand, rand)
← Back to All Questions