LeetCode 710: Random Pick with Blacklist Solution

Master LeetCode problem 710 (Random Pick with Blacklist), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

710. Random Pick with Blacklist

Hard

Array Hash Table Math Binary Search Sorting Randomized

Problem Explanation

Explanation

To solve this problem efficiently, we can map the valid numbers in the range [0, n - 1] to the numbers that are not present in the blacklist. We can achieve this by creating a mapping from each valid number to a corresponding valid number not in the blacklist.

We first need to determine the number of valid numbers in the range [0, n - 1] that are not in the blacklist. Let's denote this count as valid_count. We then need to map each valid number to a corresponding valid number not in the blacklist.

Algorithm:

Create a set blacklist_set to store all blacklisted numbers.
Calculate valid_count = n - blacklist.length.
Create a mapping from each valid number to a corresponding valid number not in the blacklist.
When picking a random number, generate a random number between 0 and valid_count - 1.
If the random number is not in the blacklist_set, return it; otherwise, map it to a valid number not in the blacklist and return that number.

Time Complexity: O(b) on average for each pick operation, where b is the length of the blacklist array.

Space Complexity: O(b) to store the blacklist set.

Solution Code

import java.util.*;

class Solution {
    Set<Integer> blacklistSet;
    int validCount;

    public Solution(int n, int[] blacklist) {
        blacklistSet = new HashSet<>();
        for (int num : blacklist) {
            blacklistSet.add(num);
        }
        validCount = n - blacklist.length;
    }

    public int pick() {
        int randomNum = (int) (Math.random() * validCount);
        if (blacklistSet.contains(randomNum)) {
            return mapToValidNumber(randomNum);
        }
        return randomNum;
    }

    private int mapToValidNumber(int num) {
        // Maps blacklisted number to a valid number not in the blacklist
        while (blacklistSet.contains(validCount + num)) {
            num = (num + 1) % validCount;
        }
        return validCount + num;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 710 (Random Pick with Blacklist)?

This page provides optimized solutions for LeetCode problem 710 (Random Pick with Blacklist) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 710 (Random Pick with Blacklist)?

The time complexity for LeetCode 710 (Random Pick with Blacklist) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 710 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 710 in Java, C++, or Python.

Back to LeetCode Solutions