# Random Pick with Blacklist

This page explains Java solution to problem `Random Pick with Blacklist` using `HashMap` data structure.

## Problem Statement

Given a blacklist `B` containing unique integers from `[0, N)`, write a function to return a uniform random integer from `[0, N)` which is NOT in `B`.

Optimize it such that it minimizes the call to systemâ€™s Math.random().

Example 1:

Input:
["Solution","pick","pick","pick"]
[[1,[]],[],[],[]]
Output: [null,0,0,0]

Example 2:

Input:
["Solution","pick","pick","pick"]
[[2,[]],[],[],[]]
Output: [null,1,1,1]

Example 3:

Input:
["Solution","pick","pick","pick"]
[[4,[2]],[],[],[]]
Output: [null,1,3,1]

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class RandomPickWithBlacklist {
/**
Idea is to shift the whitelisted number up and
take the random index from 0 to whitelisted.length

For e.g. N = 6
blacklist = {2, 3, 4}

1, 2, 3, 4, 5, 6
w  b  b  b  w  w

Only 3 whitelisted,
so swap 2 with 5 & swap 3 with 6

Which make the arr
1, 5, 6, 4, 2, 3
w  w  w  b  b  b

And then take random number from 0 - whitelisted.length
*/
private Random random = new Random();
private HashMap<Integer, Integer> blacklistedMapping = new HashMap<>();
private int blen = 0;
private int wlen = 0;
public RandomPickWithBlacklist(int N, int[] blacklist) {
this.blen = blacklist.length;
this.wlen = N - blen;

HashSet<Integer> set = new HashSet<>();
for(int i = wlen; i <= N; i++) set.add(i);

for(int blacklisted: blacklist) set.remove(blacklisted);

//Map blacklisted Indexes to One of the Whitelisted Indexes
Iterator<Integer> itr = set.iterator();
for(int i = 0; i < blen; i++) {
if(blacklist[i] < wlen) {
blacklistedMapping.put(blacklist[i], itr.next());
}
}
}

public int pick() {
int rIndex = random.nextInt(wlen);
return blacklistedMapping.getOrDefault(rIndex, rIndex);
}
}

/**
* Your RandomPickWithBlacklist object will be instantiated and called as such:
* RandomPickWithBlacklist obj = new RandomPickWithBlacklist(N, blacklist);
* int param_1 = obj.pick();
*/
``````

O(1)

O(1)