Random Pick with Blacklist - Practice Coding Problems

Random Pick with Blacklist - Problem

Array Hash Table Math Binary Search Sorting Randomized Hard

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 7, blacklist = [2, 3, 5]

› Output: Random valid number from {0, 1, 4, 6}

💡 Note: Valid numbers are 0, 1, 4, 6. Each should be returned with equal probability 1/4.

Example 2 — Small Range

$ Input: n = 4, blacklist = [1]

› Output: Random valid number from {0, 2, 3}

💡 Note: Only number 1 is blacklisted, so valid choices are 0, 2, 3 with probability 1/3 each.

Example 3 — Empty Blacklist

$ Input: n = 3, blacklist = []

› Output: Random valid number from {0, 1, 2}

💡 Note: No blacklist means all numbers 0, 1, 2 are valid with equal probability 1/3.

Constraints

1 ≤ n ≤ 10⁹
0 ≤ blacklist.length ≤ min(10⁵, n - 1)
0 ≤ blacklist[i] < n
All values in blacklist are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Range [0, n-1] with blacklisted numbers

Challenge

Pick random valid number efficiently

Output

Random number not in blacklist

Key Takeaway

🎯 Key Insight: Map blacklisted positions to valid tail positions to avoid rejection sampling and achieve O(1) pick time

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The optimal solution uses virtual mapping where blacklisted positions in range [0, M-1] map to valid positions in [M, n-1], where M = n - blacklist.length. This ensures O(1) pick() time with exactly one random call. Time: O(k) initialization, O(1) pick. Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search with Index Adjustment	O(n)	O(n-k)	Build whitelist array and use binary search for efficient random selection
Virtual Whitelist Mapping	O(k)	O(k)	Map blacklisted positions to valid positions in the tail
Brute Force - Keep Trying	O(∞)	O(k)	Generate random numbers until we find one not in blacklist

Binary Search with Index Adjustment — Algorithm Steps

Build sorted whitelist of all non-blacklisted numbers
Generate random index in [0, whitelist.length-1]
Return whitelist[random_index] directly

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Whitelist

Collect all valid numbers into array

Generate Random Index

Pick random position in whitelist

Return Value

Return whitelist[random_index]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct {
    int* whitelist;
    int whitelistSize;
} Solution;

int isInBlacklist(int* blacklist, int blacklistSize, int num) {
    for (int i = 0; i < blacklistSize; i++) {
        if (blacklist[i] == num) {
            return 1;
        }
    }
    return 0;
}

Solution* createSolution(int n, int* blacklist, int blacklistSize) {
    Solution* sol = (Solution*)malloc(sizeof(Solution));
    sol->whitelist = (int*)malloc(n * sizeof(int));
    sol->whitelistSize = 0;
    
    for (int i = 0; i < n; i++) {
        if (!isInBlacklist(blacklist, blacklistSize, i)) {
            sol->whitelist[sol->whitelistSize++] = i;
        }
    }
    
    srand(time(NULL));
    return sol;
}

int pick(Solution* sol) {
    int idx = rand() % sol->whitelistSize;
    return sol->whitelist[idx];
}

int solution(int n, int* blacklist, int blacklistSize) {
    Solution* sol = createSolution(n, blacklist, blacklistSize);
    int result = pick(sol);
    free(sol->whitelist);
    free(sol);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %s", line);
    
    int blacklist[1000];
    int blacklistSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        blacklist[blacklistSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(n, blacklist, blacklistSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Initialization takes O(n) to build whitelist, pick() is O(1)

✓ Linear Growth

Space Complexity

O(n-k)

Whitelist array stores all n-k valid numbers

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search with Index Adjustment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler