How do you solve Random Pick with Blacklist on LeetCode?

Random Pick with Blacklist (LeetCode #710) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(m) space complexity. Key insight: Using a mapping allows for efficient retrieval of valid numbers.

What is the brute force solution for Random Pick with Blacklist?

The brute force approach for Random Pick with Blacklist is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating random numbers in the range [0, n-1] and checking if they are in the blacklist. If the number is blacklisted, we continue generating until we find a valid number. This is simple but inefficient. The optimal Optimal Solution approach improves this to O(1).

What are the interview tips for Random Pick with Blacklist?

Explain your thought process clearly when discussing the brute-force approach. Discuss the trade-offs of different approaches, especially in terms of time and space complexity. Practice explaining your code as you write it to simulate the interview environment.

What are common mistakes when solving Random Pick with Blacklist?

Not handling the edge cases where the blacklist covers most of the range. Failing to ensure uniform distribution in random picks.

#710

Random Pick with Blacklist

Hard

ArrayHash TableMathBinary SearchSortingRandomizedHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(m)

💡

Intuition

Time O(1)Space O(m)

The optimal approach uses a mapping of blacklisted numbers to valid numbers, allowing us to efficiently pick from the valid range without repeatedly generating numbers. This reduces the number of calls to the random function significantly.

⚙️

Algorithm

4 steps

1Step 1: Create a set of blacklisted numbers and a mapping of blacklisted numbers to valid numbers.
2Step 2: Calculate the number of valid numbers as n - size of blacklist.
3Step 3: Generate a random number in the range [0, valid_count - 1].
4Step 4: If the random number is less than valid_count, return it directly. Otherwise, map it to a valid number using the mapping.

solution.py19 lines

1import random
2from sortedcontainers import SortedList
3
4class Solution:
5    def __init__(self, n: int, blacklist: List[int]):
6        self.n = n
7        self.blacklist = set(blacklist)
8        self.valid_count = n - len(blacklist)
9        self.map_blacklist = {}
10        for b in blacklist:
11            if b >= self.valid_count:
12                while self.valid_count in self.blacklist:
13                    self.valid_count += 1
14                self.map_blacklist[b] = self.valid_count
15                self.valid_count += 1
16
17    def pick(self) -> int:
18        num = random.randint(0, self.valid_count - 1)
19        return self.map_blacklist.get(num, num)

ℹ

Complexity note: The time complexity is O(1) for picking a number since we only generate one random number and check the mapping. Space complexity is O(m) where m is the size of the blacklist, used for storing the mappings.

1Using a mapping allows for efficient retrieval of valid numbers.
2Understanding the distribution of valid numbers is crucial for random selection.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.