Simple Solution using hash map in C++
Intuition\nThe intuition behind this approach is to randomly pick an index (i, j) in the binary grid where the value is 0 and return it. To ensure that all indi
# Intuition\nThe intuition behind this approach is to randomly pick an index `(i, j)` in the binary grid where the value is `0` and return it. To ensure that all indices where the value is `0` are equally likely to be returned, we use a map `mp` to keep track of the occurrences of each index. If an index has already been flipped to `1`, we regenerate another random index until we find an index that hasn\'t been flipped yet.\n\n# Approach\n1. In the constructor `Solution(int m, int n)`, we initialize the dimensions of the binary grid (`m` rows and `n` columns).\n2. In the `flip()` function, we generate random indices `i` and `j` within the range `[0, m)` and `[0, n)` respectively.\n3. We check if the selected index `(i, j)` has already been flipped to `1`. If it has, we regenerate random indices until we find an index that hasn\'t been flipped yet.\n4. Once we find a valid index, we mark it as flipped by incrementing its count in the map `mp` and return the index `(i, j)`.\n5. In the `reset()` function, we clear the map `mp` to reset the state of the grid.\n\n# Complexity\n- Time complexity:\n  - The `flip()` function has an expected time complexity of $$O(1)$$ for each call, as generating random indices and checking their presence in the map takes constant time on average.\n  - The `reset()` function has a time complexity of $$O(1)$$ as it clears the map.\n- Space complexity:\n  - The space complexity is $$O(k)$$, where `k` is the number of unique indices flipped to `1`. This is because the map `mp` stores the count of each flipped index. However, in the worst case, where all indices are flipped, the space complexity becomes $$O(m \\times n)$$, where `m` is the number of rows and `n` is the number of columns in the grid.\n# Code\n```\n#include<bits/stdc++.h>\nclass Solution {\n    int m, n;\n    map<pair<int, int>, int> mp;\npublic:\n    Solution(int m, int n) {\n        this -> m = m;\n        this -> n = n;\n    }\n    \n    vector<int> flip() {\n        int i = rand() % m;\n        int j = rand() % n;\n\n        while(mp[{i,j}]>0)\n        {\n            i = rand() % m;\n            j = rand() % n;\n        }\n\n        mp[{i, j}]++;\n        return {i, j};\n    }\n    \n    void reset() {\n        mp.clear();\n    }\n};\n```
['Hash Table', 'Math', 'Matrix', 'C++']