Python solution based on random shuffle with explanation
This is a sampling n elements without replacement problem. It is the same as the operation that random shuffe an array and then return the first n elements. \n\
This is a sampling n elements without replacement problem. It is the same as the operation that random shuffe an array and then return the first n elements. \n\nHere come the trick. When we random pick an element in the array we can store its new position in a hash table instead of the array because n is extremely less than the total num. So we can accomplish this within O(1) time and O(k) space where k is the maxium call of flip.\n\n```\nclass Solution:\n\n    def __init__(self, n_rows, n_cols):\n        """\n        :type n_rows: int\n        :type n_cols: int\n        """\n        self.c = n_cols\n        self.end = n_rows * n_cols - 1\n        self.d = {}\n        self.start = 0\n        \n    def flip(self):\n        """\n        :rtype: List[int]\n        """\n        rand = random.randint(self.start, self.end)\n        res = self.d.get(rand, rand)\n        self.d[rand] = self.d.get(self.start, self.start)\n        self.start += 1\n        return divmod(res, self.c)\n    \n    def reset(self):\n        """\n        :rtype: void\n        """\n        self.d = {}\n        self.start = 0\n```
[]