C++ with explanation
The idea is to maintain a pointer to the last element. Each time we select within the range of [0 , last].\nif the selected one is not the last, we swap it with
The idea is to maintain a pointer to the last element. Each time we select within the range of [0 , last].\nif the selected one is not the last, we swap it with the last and use a map to record this mapping . \nAfter that, we decrease the last pointer by one. \nEssentially, we move the unselected last to the position selected. \n\nNext time, we randomly select from [0, last] again and find k. if k is mapped to a previously swapped last, We return the mapped one. \n\n```\nclass Solution {\n    // algorithm: swap the selected one with the last one, establish a mapping\n    int last;\n    int row, col; \n    unordered_map<int, int> dict; \npublic:\n    Solution(int n_rows, int n_cols) {\n        row=n_rows;\n        col=n_cols;         \n       reset();\n    }\n    \n    vector<int> flip() {\n        int orig_val = rand()%(last+1);\n        int ret_val=orig_val; \n        \n        if (dict.count(orig_val)!=0)\n            ret_val= dict[orig_val];\n        \n        //swap with current last element\n        // update the mapping\n        \n        // if selected one is already the last one, no swap action needed\n        if (orig_val != last)\n        {        \n           if (dict.count(last)==0)\n                dict[orig_val]=last;\n            else\n                dict[orig_val]=dict[last];\n        }\n        last--; \n        return {ret_val/col, ret_val%col };\n    }\n    \n    void reset() {\n        last = row*col -1; \n        dict.clear();\n    }\n};\n```
[]