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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Random Pick with Blacklist

Number: 894

Difficulty: Hard

Paid? No

Companies: Amazon, Google, Uber

Problem Description

Given an integer n and a list of unique integers called blacklist, design an algorithm to pick a random integer from the range [0, n - 1] that is not in the blacklist. Every valid integer (i.e. not blacklisted) should have an equal probability of being chosen. The goal is to optimize the solution to minimize calls to the built-in random function.

Key Insights

  • The valid output range has a total count of available numbers W = n - len(blacklist).
  • Instead of repeatedly generating random numbers and checking against a set, we can transform the range into a contiguous block [0, W - 1] and map any blacklist number within that block to a valid number in the upper range.
  • Mapping is precomputed: for any blacklisted number x in [0, W-1], assign it a valid number from [W, n-1] that is not blacklisted.
  • This approach ensures O(1) pick time after an O(b) precomputation where b = length of blacklist.

Space and Time Complexity

Time Complexity: constructor - O(b) for initializing data structures, pick() - O(1) per call.
Space Complexity: O(b) for storing the blacklist set and mapping.

Solution

We compute the count of valid numbers, W = n - len(blacklist). For numbers in the blacklist that are less than W, we need to map them to a valid number from the range [W, n-1]. To do this, we first store all blacklist numbers in the higher range [W, n-1] in a set for quick lookup. Then for each blacklisted value in [0, W-1], we iterate from W upwards to find a number that is not blacklisted and assign it in a mapping. During the pick() function, we generate a random integer r in [0, W-1]. If r is in our mapping, we return its corresponding mapped value; otherwise, we return r as it is already a valid number.

Code Solutions

import random

class Solution:
    def __init__(self, n: int, blacklist: list):
        # Total numbers valid for picking
        self.W = n - len(blacklist)
        # Mapping for blacklisted numbers in the valid range
        self.mapping = {}
        # Set to hold blacklisted numbers that are >= W
        blacklist_set = set(blacklist)
        
        # Pointer to find available numbers in [W, n-1]
        available = self.W
        for b in blacklist:
            if b < self.W:
                # Find next available non-blacklisted number in the tail region.
                while available in blacklist_set:
                    available += 1
                self.mapping[b] = available
                available += 1
        
    def pick(self) -> int:
        # Generate a random number in the range [0, self.W-1]
        idx = random.randint(0, self.W - 1)
        # If the number is mapped, return the mapping; else it is valid.
        return self.mapping.get(idx, idx)
← Back to All Questions