from two-pointer to MLE to remapping solution

\n\nIf we want to pick uniformly random, the underlying API would be something like `Random.nextInt(bound)`. So how could we use this API to pick non-blacklist numbers? We can store those numbers in some random access data structure like array `pool`, then `Random.nextInt(pool.length)` would do the trick.\n\nHow could we end up with such a `pool`? One way is to partition an array with length `n`, such that all blacklisted numbers are at the end of the array. How can we do that? We can use two-pointers `i` `j`, where `i` is always `0`, and maintain the loop invariant that `pool[j+1..]` are all blacklist numbers. In particular we init `pool` with identity mapping, i.e. `pool[i] = i;`. We process `blacklist` in **descending** order, for each `b` swapping `pool[b]` with `pool[j]` then decrement `j`.\n``` java\nclass Solution {\n\tint[] pool;\n int poolLen;\n Random seed;\n \n public Solution(int n, int[] blacklist) {\n \tArrays.sort(blacklist);\n \tthis.seed = new Random();\n \tthis.pool = new int[n];\n\t\tthis.poolLen = n - blacklist.length;\n \t/* init as id map */\n \t\tfor (int i = 0; i < this.pool.length; i++) {\n \t\t\tthis.pool[i] = i;\n \t\t}\n \t\t/* two pointer to partition blacklist at pool end */\n \t\tint poolEnd = this.pool.length-1;\n \t\tfor (int i = blacklist.length-1; i >= 0; i--) {\n \t\t\tfinal int val = blacklist[i];\n \t\t\t/* still in id map => index pool[val] */\n \t\t\t/* swap with the other pointer */\n \t\t\tint temp = this.pool[poolEnd];\n \t\t\tthis.pool[poolEnd] = this.pool[val];\n \t\t\tthis.pool[val] = temp;\n \t\t\tpoolEnd--;\n \t\t}\n \t}\n \n \tpublic int pick() {\n \t\tint i = this.seed.nextInt(this.poolLen);\n \t\treturn this.pool[i];\n \t}\n}\n```\n\nThis is all good until I got **Memory Limit Exceeded**. The test case is roughly like no. 66/68: [n=1e9, blacklist=[6838038]]. So `pool` uses too much memory.\n\nHow could we space optimization on such cases? I noticed that for all "untouched" indices in `pool`, they remain identity mapping (`pool[i] == i`). These are non-blacklisted numbers. So rather than maintaining a mapping for those numbers, we could instead maintain the mapping for blacklist numbers, which uses max space `1e5` as indicated by input size constraints.\n\nBelow are final accepted solution. The algorithm is the same, just that I did mapping of blacklist numbers instead to save memory.\n\n``` java\nclass Solution {\n\tHashMap map;\n\tint poolLen;\n\tRandom seed;\n\n\tpublic Solution(int n, int[] blacklist) {\n\t\tArrays.sort(blacklist);\n\t\tthis.seed = new Random();\n\t\tthis.map = new HashMap<>();\n\t\tthis.poolLen = n - blacklist.length;\n\t\t/* two pointer to partition blacklist at pool end */\n\t\tint poolEnd = n-1;\n\t\tfor (int i = blacklist.length-1; i >= 0; i--) {\n\t\t\tfinal int val = blacklist[i];\n\t\t\t/* swapping */\n\t\t\tif (!this.map.containsKey(poolEnd)) {\n\t\t\t\t/* `poolEnd` is id map */\n\t\t\t\tthis.map.put(val, poolEnd);\n\t\t\t} else {\n\t\t\t\t/* `flatten\' chain map */\n\t\t\t\tthis.map.put(val, this.map.get(poolEnd));\n\t\t\t\t/* no need this key */\n\t\t\t\tthis.map.remove(poolEnd);\n\t\t\t}\n\t\t\tpoolEnd--;\n\t\t}\n\t}\n\n\tpublic int pick() {\n\t\tint i = this.seed.nextInt(this.poolLen);\n\t\tif (this.map.containsKey(i)) {\n\t\t\t/* blacklist */\n\t\t\treturn this.map.get(i);\n\t\t}\n\t\t/* whitelist: id map */\n\t\treturn i;\n\t}\n}\n```\n\n

Complexity

\nTime Complexity\n\n`O(nlogn)`\n\nSpace Complexity\n`O(blacklist.length)`\n

Random Pick with Blacklist

Problem Description

Problem Description

Answer Panel