#710

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Random Pick with Blacklist

Random Pick with Blacklist requires designing a method to uniformly pick integers while excluding blacklisted values efficiently.

array hash table math binary search sorting

Problem Statement

You are given an integer n and a unique integer array blacklist. Design a data structure that allows picking a random integer from [0, n - 1] that is not present in blacklist. Each valid integer should have an equal chance of being returned on each call.

Optimize the implementation to minimize the number of calls to the built-in random generator. Implement a class Solution with a constructor accepting n and blacklist, and a pick() method that returns a valid random integer efficiently, even when blacklist is large.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []] Output [null, 0, 4, 1, 6, 1, 0, 4]

Explanation Solution solution = new Solution(7, [2, 3, 5]); solution.pick(); // return 0, any integer from [0,1,4,6] should be ok. Note that for every call of pick, // 0, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/4). solution.pick(); // return 4 solution.pick(); // return 1 solution.pick(); // return 6 solution.pick(); // return 1 solution.pick(); // return 0 solution.pick(); // return 4

Constraints

1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <= blacklist[i] < n
All the values of blacklist are unique.
At most 2 * 104 calls will be made to pick.

Solution Approach

Map Blacklisted Values

Use a hash table to map blacklisted numbers in the lower range to valid numbers in the upper range. This allows skipping blacklisted indices while maintaining O(1) pick time.

Random Selection Within Valid Range

Generate a random integer between 0 and n - blacklist.length - 1. If the value maps to a blacklisted index, use the precomputed hash mapping to get a valid integer.

Optimize for Space and Calls

Only store mappings for blacklisted numbers that fall in the random selection range. This reduces space usage and minimizes the number of random function calls required.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) per pick after O(B) preprocessing where B is the blacklist length. Space complexity is O(B) for the hash map storing remapped values.

What Interviewers Usually Probe

Emphasize minimizing random function calls while ensuring uniform distribution.
Check if the candidate maps blacklisted indices correctly instead of scanning every time.
Look for clear reasoning on hash map usage and upper-lower range mapping.

Common Pitfalls or Variants

Common pitfalls

Attempting to randomly pick and retry until valid, which is inefficient for large n and blacklist.
Not mapping blacklisted numbers that fall in the random pick range, leading to incorrect probabilities.
Overusing space by mapping all blacklist numbers instead of only those needed for O(1) access.

Follow-up variants

Pick multiple random integers without replacement while respecting the blacklist.
Blacklist is dynamic and can change between picks, requiring dynamic remapping.
Support weighted random picks among non-blacklisted numbers instead of uniform selection.

FAQ

How does Random Pick with Blacklist differ from standard random selection?

Standard random selection picks any integer uniformly. Here, the algorithm must exclude blacklisted integers while keeping each valid number equally likely.

Why use a hash map for blacklist remapping?

It allows O(1) access to map blacklisted indices in the pick range to valid integers, ensuring efficient and uniform random picks.

Can this method handle very large n?

Yes, since the approach only stores mappings for blacklisted numbers in the random range, space remains O(blacklist.length) regardless of n.

What happens if the blacklist is empty?

The algorithm simplifies to a standard random pick from 0 to n - 1, and no hash mapping is required.

Is the random selection truly uniform?

Yes, the remapping ensures each non-blacklisted integer in [0, n - 1] has an equal probability of being returned on each pick.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

Continue Practicing

#268 missing number #792 number of matching subsequences #532 k diff pairs in an array