Leetcode Problem 710. Random Pick with Blacklist

710. Random Pick with Blacklist

Leetcode Solutions

Approach: Virtual Whitelist

  1. Initialize a HashMap mapping to store the remapping of blacklisted to whitelisted numbers.
  2. Sort the blacklist array.
  3. Split the blacklist into two parts: blacklist1 with numbers less than n - len(blacklist) and blacklist2 with the rest.
  4. Create a list whitelist of all numbers in the range [n - len(blacklist), n) that are not in blacklist2.
  5. Iterate over blacklist1 and map each number to a corresponding number in whitelist using mapping.
  6. When pick() is called, generate a random index in [0, n - len(blacklist)).
  7. If the random index is not in mapping, return it; otherwise, return the mapped value from mapping.
UML Thumbnail

Approach: Whitelist

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...