Skip to main content
Talentd

Random Pick with Blacklist - Solution & Explanation

HardArrayHash TableMathBinary Search8 min readAsked at: Amazon, Uber, Google
Practice this problem

Problem Statement

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.

Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language.

Implement the Solution class:

  • Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist.
  • int pick() Returns a random integer in the range [0, n - 1] and not in blacklist.

 

Example 1:

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.

Approach Overview

Problem Overview: You need to randomly return an integer from the range [0, n) while excluding numbers listed in a blacklist. Every valid number must have equal probability. The challenge is avoiding blacklisted values without repeatedly generating random numbers and rejecting them.

Approach 1: Binary Search on Sorted Blacklist (Pick: O(log b), Preprocess: O(b log b))

Sort the blacklist first. Instead of picking from [0, n), pick a random index k from the range [0, n - b) where b is the blacklist size. This represents the index of the k-th valid number if the blacklist didn’t exist. Use binary search on the sorted blacklist to determine how many blacklisted numbers are less than or equal to the candidate value and shift the result accordingly. The key insight: each blacklisted value "pushes" valid numbers forward. Binary search efficiently finds how many pushes occur. Sorting dominates preprocessing at O(b log b), and each random pick costs O(log b). Space complexity is O(b). This approach relies on binary search and works well when the blacklist is static.

Approach 2: Hash Map with Remapping (Pick: O(1), Preprocess: O(b))

The optimal solution remaps blacklisted values that fall inside the valid picking range. Let m = n - b. Generate random numbers only from [0, m). If a blacklisted number appears inside this range, map it to a safe number from the upper range [m, n) that is not blacklisted. Build a hash map where each blocked value in the lower range points to a valid replacement. During pick(), generate a random integer x in [0, m). If x exists in the map, return the mapped value; otherwise return x. Preprocessing scans the blacklist and uses a set or map for constant-time checks, resulting in O(b) time and space. Each random pick runs in O(1). This method heavily uses hash tables and randomized selection concepts from randomized algorithms. It guarantees uniform distribution across valid numbers.

Recommended for interviews: The hash map remapping approach is what most interviewers expect because it achieves O(1) pick time while keeping preprocessing linear. Explaining the binary search idea first shows you understand the indexing trick of skipping blacklisted values. Implementing the remapping solution demonstrates strong command of array indexing, hashing, and probability correctness.

Approach 1: Binary Search on Sorted Blacklist

This approach involves preprocessing the blacklist by sorting it. Upon calling 'pick', we randomly select a number from 0 to n - blacklist.length - 1 and adjust it using binary search to account for blacklisted numbers.

In this Python solution, the 'bisect_left' function is used to find the number of blacklisted numbers less than the current random number, thus adjusting it directly to a safe number.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(log B) per pick call, where B is the length of blacklist.
Space Complexity: O(B) due to storage of the blacklist.

Try this approach in the editor →

Approach 2: Hash Map with Mapping

This approach involves creating a mapping from blacklisted numbers under n-k (where k is the list length) to valid un-blacklisted numbers above that range. This method efficiently handles cases when n is large but the blacklist is relatively small.

This JavaScript solution initializes the mapping in the constructor, so invalid values in the lower range are mapped to available numbers in the higher ones. The pick method then uses this map to return a correct answer efficiently.

Code

JavaScriptC++

JavaScript

C++

Complexity

Time Complexity: O(1) per pick call.
Space Complexity: O(B) where B is the size of the blacklist.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search on Sorted Blacklist

Time Complexity: O(log B) per pick call, where B is the length of blacklist.
Space Complexity: O(B) due to storage of the blacklist.

Hash Map with Mapping

Time Complexity: O(1) per pick call.
Space Complexity: O(B) where B is the size of the blacklist.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search on Sorted BlacklistPreprocess: O(b log b), Pick: O(log b)O(b)When the blacklist is static and binary search logic is acceptable for each pick
Hash Map with RemappingPreprocess: O(b), Pick: O(1)O(b)Best general solution when frequent random picks are required

Video Solution

Random Pick with blacklist || Leetcode • Pepcoding • 3,185 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Random Pick with Blacklist easy or hard?
Random Pick with Blacklist is classified as a Hard problem on LeetCode. The difficulty comes from designing a constant-time random picker while preserving uniform probability across all valid numbers.
How to solve Random Pick with Blacklist in O(n)?
Use a remapping technique with a hash map. Compute m = n - blacklist.size() and only generate random numbers in [0, m). Any blacklisted number inside this range is mapped to a valid number in [m, n). Building this mapping requires O(b) time and space.
What is the best approach for Random Pick with Blacklist?
The hash map remapping approach is the optimal solution. It preprocesses the blacklist in O(b) time and ensures each call to pick() runs in O(1). Blacklisted numbers in the lower selection range are mapped to valid numbers in the upper range, guaranteeing uniform randomness.
What data structure is used in Random Pick with Blacklist?
The optimal solution uses a hash map and a hash set. The set tracks blacklisted values, while the map remaps blocked indices in the lower range to valid numbers in the upper range. Some alternative implementations also use sorted arrays with binary search.
What is the time complexity of Random Pick with Blacklist?
The optimal hash map solution runs preprocessing in O(b) time and space, where b is the blacklist size, and each pick() call runs in O(1). A binary search alternative requires O(b log b) preprocessing and O(log b) time per random pick.
Random Pick with Blacklist Python or Java solution approach
Both Python and Java implementations follow the same logic. Precompute m = n - blacklist.length, map invalid indices in [0, m) to valid values in [m, n), and during pick() generate a random integer in [0, m). Return the mapped value if it exists, otherwise return the random number.
Is Random Pick with Blacklist asked at Google, Amazon, or Meta?
Randomized data structure problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests hash map usage, probability correctness, and efficient preprocessing for repeated queries.

Ready to solve this problem?

Practice Random Pick with Blacklist with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Unique Binary String

Next

Random Pick Index