Knuth Shuffle | C++ | call one rand per flip
Intuition\n Describe your first thoughts on how to solve this problem. \nThis uses the least number of rand() for per flip. The idea is based on knuth shffling.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis uses the least number of rand() for per flip. The idea is based on knuth shffling. Knuth Shuffle is a well known algorithm to shuffle an array.\n\n```\n    for i from last down to 1 do:\n            let j = random integer in range 0 <= j <= i\n            swap items[i] with items[j]\n```\n\nThe intution is to pick a random index to flip then swap it with the last index that hasn\'t been swapped. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe first want to create 1-D array from 2-D array, then we will perform sampling using Knuth Suffle idea. For an index $(x,y)$ we can map it to index $(x\\cdot n + y)$ in 1-D array of size $m\\cdot n$.\n\nNow that we have 1-D array we will perform the sampling. There are at least two ways to implement the idea. \n\n1. We can create an array of size $m\\cdot n$. For each call of `flip()`, we pick a random element in an array, and swap it with last index and return the picked value. Then shrink the size of the array by 1. We can put back the total size back to $m\\cdot n$ for `reset()`. Note that we do not need to put all indices back into place for reset.\n\n2. Another approach is to have a hashmap for chosen index. We pick a random number less than remaining indicies (starting $m\\cdot n$), then number is no replaced with lastIndex. After the first iteration, we have to check whether the chosen value is already picked and replaced by some other value in hash_map. \n\nThe 1st approach always creates $O(mn)$ size array, thus it will run out of memory, whereas the 2nd approach will only hit $O(mn)$ space if it makes $O(mn)$ calls of `flip()`. Therefore we will code the 2nd approach. In the code I swapped the chosen element with the least significiant index that hasn\'t been swapped. Also, note that we have to shorten the hash_map to make sure we do not create linked-list of size $m\\cdot n$.\n\n# Complexity\n- Time complexity: $$O(1)$$, for each flip it needs on `rand()` call and two map look ups.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity: $$O(nm)$$, hash map can be as big as $m\\cdot n$ in worst case.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nprivate:\n    int n;\n    int total;\n    int flipped;\n    unordered_map<int, int> flipmap;\n\n    inline vector<int> getIndex(int key) {\n        return vector<int>({key/n, key%n});\n    }\n\npublic:\n    Solution(int m, int _n) {\n        n = _n;\n        total = m*n;\n        flipped = 0;\n        flipmap.clear();\n    }\n    \n    vector<int> flip() {\n        int k = rand() % (total - flipped) + flipped;\n\n        int key = (flipmap.count(k) > 0) ? flipmap[k] : k;\n        flipmap[k] = (flipmap.count(flipped) > 0) ? flipmap[flipped] : flipped;\n        flipped++;\n\n        return getIndex(key);\n    }\n    \n    void reset() {\n        flipmap.clear();\n        flipped = 0;\n    }\n};\n```
['C++']