Java | FYS Algo | Explained
Idea:\n This is the Fisher\u2013Yates shuffle algorithm\n Numbers in a grid can be mapped out to a 1D array like this. This array would be of size n = rows x co
**Idea:**\n* This is the [Fisher\u2013Yates shuffle algorithm](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)\n* Numbers in a grid can be mapped out to a 1D array like [this](https://softwareengineering.stackexchange.com/questions/212808/treating-a-1d-data-structure-as-2d-grid). This array would be of size n = rows x columns\n* Use a hashMap (M) from index to num mimicking a dynamic array\n* Pick a random number `i` in [0, n). This will be the index of our random number R\n* Number of available picks (A) reduce by 1\n* Since there is no actual array in memory so `i` may not exist in M. If it doesn\'t exist in M, then use i as R. This works because indices and numbers are initially all equal and in the range [0, n)\n* Now you have a random number (R) from the array. Swap it with the tail of array (A)\n* Tail of array may not exist in M, so default it to A\n* Return the result\n>T/S: \n>*constructor*: O(1)/O(1)\n>*reset*: O(1)/O(1)\n>each call to *flip*: O(1)/O(1)\n>Space grows linearly with calls to flip, i.e. f calls to flip will grow space to O(f) \n```\nclass Solution {\n\tprivate static final Random random = new Random();\n\t\n\tprivate final int total;\n\tprivate final int n;\n\t\n\tprivate Map<Integer, Integer> indexToNum = new HashMap<>();\n\tprivate int available;\n\n\t/**\n\t * Initializes the object with the size of the binary matrix m and n\n\t *\n\t * @param m rows\n\t * @param n columns\n\t */\n\tpublic Solution(int m, int n) {\n\t\tthis.n = n;\n\t\ttotal = available = m * n;\n\t}\n\n\t/**\n\t * @return a random index [i, j] of the matrix where matrix[i][j] == 0 and flips it to 1\n\t */\n\tpublic int[] flip() {\n\t\tvar randomIndex = random.nextInt(available--);\n\t\tvar numAtRandomIndex = indexToNum.getOrDefault(randomIndex, randomIndex);\n\t\tvar tail = indexToNum.getOrDefault(available, available);\n\t\tindexToNum.put(randomIndex, tail); // swap\n\t\treturn new int[]{numAtRandomIndex / n, numAtRandomIndex % n};\n\t}\n\n\t/**\n\t * Resets all the values of the matrix to be 0.\n\t */\n\tpublic void reset() {\n\t\tavailable = total;\n\t\tindexToNum = new HashMap<>();\n\t}\n}\n```\n***Please upvote if this helps***
['Java']