Introduction

In this blog post, we will explore how to solve the LeetCode problem "710" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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.

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Mapping Blacklisted Integers: The core idea is to map blacklisted integers in the range [0, n - len(blacklist)) to valid (non-blacklisted) integers in the range [n - len(blacklist), n). This effectively moves the "holes" created by the blacklist to the end of the range.
• Random Number Generation: Generate a random integer within the reduced range [0, n - len(blacklist)).

• Lookup and Return: If the generated random number is in the mapping, return its mapped value. Otherwise, return the random number itself (since it's a valid, non-blacklisted integer).

• Time Complexity: O(B) for initialization, O(1) for pick(). Where B is the length of the blacklist.

• Space Complexity: O(B)

Code

    import random

class Solution:
    def __init__(self, n: int, blacklist: list[int]):
        self.n = n
        self.blacklist = blacklist
        self.blacklist_size = len(blacklist)
        self.valid_size = n - self.blacklist_size
        self.mapping = {}

        blacklist_set = set(blacklist)
        valid_end = self.valid_size

        for b in blacklist:
            if b < self.valid_size:
                while valid_end < n and valid_end in blacklist_set:
                    valid_end += 1
                if valid_end < n:
                    self.mapping[b] = valid_end
                    valid_end += 1

    def pick(self) -> int:
        random_index = random.randint(0, self.valid_size - 1)
        if random_index in self.mapping:
            return self.mapping[random_index]
        else:
            return random_index