Problem

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.

OR

Given an integer n and a list of integers l, write a function that randomly generates a number from 0 to n-1 that isn’t in l (uniform).

Examples

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

Solution

Method 1 - Using Hashmap

Here’s an optimized approach to solve the problem, focusing on minimizing the number of calls to the built-in random function.

Approach

  1. Initialization:
    • Create a list of valid numbers that are not in the blacklist.
    • Use a HashMap to remap blacklisted indices that fall within the valid range to available indices in the valid range.
  2. Mapping:
    • Calculate a range for valid picks by excluding blacklisted elements.
    • Map blacklisted elements that fall within the valid range to valid elements outside the valid range.
  3. Random Pick:
    • Use the built-in random function to select an integer within the valid range.
    • If the selected integer is mapped, return the remapped value, otherwise return the selected integer.

Steps

Here are the detailed steps:

  1. Filter out blacklisted numbers that are valid picks: Identify which numbers from 0 to ( n-1 ) are valid and not in the blacklist.
  2. Mapping: Map blacklisted indices to available indices outside the valid range.
  3. Random Selection: Select an index randomly from the valid range and return the appropriate element.

Code

Java
public class Solution {
    private HashMap<Integer, Integer> mapping;
    private int range;
    private Random random;

    public Solution(int n, int[] blacklist) {
        mapping = new HashMap<>();
        HashSet<Integer> blacklistSet = new HashSet<>();
        random = new Random();

        // Convert blacklist array to set for quick lookup
        for (int b : blacklist) {
            blacklistSet.add(b);
        }

        // Calculate the range of allowed numbers [0, n - blacklist.length)
        range = n - blacklist.length;

        int last = n - 1;
        // Map blacklisted numbers within the valid range to allowed numbers
        // outside the range
        for (int b : blacklist) {
            if (b < range) {
                // Find a valid number from the end to map to the current
                // blacklisted number
                while (blacklistSet.contains(last)) {
                    last--;
                }
                // Map current blacklisted number within the valid range to the
                // valid number
                mapping.put(b, last);
                last--;
            }
        }
    }

    public int pick() {
        // Pick a random number within the valid range
        int index = random.nextInt(range);
        // Remap if it's in the blacklist, otherwise return the index itself
        return mapping.getOrDefault(index, index);
    }
}

Complexity

  • ⏰ Time complexity
    • Initialization: O(b) where b is the length of the blacklist.
    • Pick: O(1)
  • 🧺 Space complexity: O(b), for storing the mapping.