Scale Engineer

Random Pick with Blacklist

Hard
#0664Time: Constructor: `O(n + B)`. The loop runs `n` times. Given `n` can be up to 10^9, this is too slow and will cause a "Time Limit Exceeded" error. `pick()`: `O(1)`.Space: `O(n - B)` to store the `whitelist`, where `B` is the blacklist size. Since `n` can be 10^9, this will cause an "Out of Memory" error.
Patterns
MathRandomized
Algorithms
Binary SearchSortingBloom Filter
Data structures
ArrayHash Table

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward idea is to generate a list of all valid numbers (the "whitelist") during initialization. The pick() method then simply selects a random element from this pre-computed list.

Algorithm

  • Initialize a HashSet from the blacklist array.
  • Initialize an ArrayList whitelist.
  • Loop from i = 0 to n-1. If i is not in the blacklist set, add it to whitelist.
  • To pick, generate a random index up to whitelist.size() and return the element at that index.

Walkthrough

In this approach, we first build a complete list of all numbers that are not in the blacklist. This is done once during the initialization of the Solution object.

Constructor (Solution(n, blacklist))

  1. First, we convert the blacklist array into a HashSet for efficient O(1) average time lookups. This helps in quickly checking if a number is blacklisted.
  2. We create a new ArrayList to store the valid numbers, let's call it whitelist.
  3. We then iterate through all numbers from 0 to n-1.
  4. For each number i, we check if it exists in the blacklist HashSet.
  5. If i is not in the blacklist, we add it to our whitelist ArrayList.

pick() Method

  1. The size of the whitelist is W, which is n - blacklist.length.
  2. We generate a random integer index in the range [0, W-1].
  3. We return the element at whitelist.get(index). All valid numbers are in the list, so picking a random index gives a uniform probability to each valid number.

This approach is simple but fundamentally flawed by the problem's constraints, where n can be up to 10<sup>9</sup>.

class Solution {    private List<Integer> whitelist;    private Random rand;     public Solution(int n, int[] blacklist) {        this.whitelist = new ArrayList<>();        this.rand = new Random();        Set<Integer> blacklistSet = new HashSet<>();        for (int b : blacklist) {            blacklistSet.add(b);        }         for (int i = 0; i < n; i++) {            if (!blacklistSet.contains(i)) {                this.whitelist.add(i);            }        }    }     public int pick() {        int randomIndex = rand.nextInt(this.whitelist.size());        return this.whitelist.get(randomIndex);    }}

Complexity

Time

Constructor: `O(n + B)`. The loop runs `n` times. Given `n` can be up to 10^9, this is too slow and will cause a "Time Limit Exceeded" error. `pick()`: `O(1)`.

Space

`O(n - B)` to store the `whitelist`, where `B` is the blacklist size. Since `n` can be 10^9, this will cause an "Out of Memory" error.

Trade-offs

Pros

  • The pick() operation is very fast, O(1).

  • The logic is simple to understand.

Cons

  • Extremely high time complexity in the constructor, making it infeasible for large n.

  • Extremely high space complexity, making it infeasible for large n.

Solutions

class Solution { private Map < Integer , Integer > d = new HashMap <>(); private Random rand = new Random (); private int k ; public Solution ( int n , int [] blacklist ) { k = n - blacklist . length ; int i = k ; Set < Integer > black = new HashSet <>(); for ( int b : blacklist ) { black . add ( b ); } for ( int b : blacklist ) { if ( b < k ) { while ( black . contains ( i )) { ++ i ; } d . put ( b , i ++); } } } public int pick () { int x = rand . nextInt ( k ); return d . getOrDefault ( x , x ); } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(n, blacklist); * int param_1 = obj.pick(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem