Reservoir sampling optimal solution.
Imagine you have an array of length n with the i-th element being i. In reservoir sampling, you keep track of the number of elements left l. In each get_next() 
Imagine you have an array of length `n` with the `i-th` element being `i`. In reservoir sampling, you keep track of the number of elements left `l`. In each `get_next()` call, `l` is first decremented and a random integer `r` is chosen in the range of `[0, l]` (inclusive), then you want to exchange the `r-th` value with the `l-th` value and return the `l-th` value after the exchange. In this way all the elements will be popped once and will have equal probability of being chosen. Then you\'ll just have to map the 1d array to a 2d matrix and you are done.\n\nI structured code in the same way so readers can better understand the situation.\n\nTime complexity O(1) each call. 1 random call per `flip`.\n\n```\nimport random\n\n\nclass ReservoirSampling:\n    def __init__(self, n):\n        self.n = n\n        self.build()\n\n    def build(self):\n        self.m = {}\n        self.l = self.n\n\n    def get_next(self):\n        self.l = self.l - 1\n        r = random.randint(0, self.l)\n        v = self.m.get(r, r)\n        self.m[r] = self.m.get(self.l, self.l)\n        return v\n\n    def reset(self):\n        self.build()\n\n\nclass Solution:\n    def __init__(self, n_rows, n_cols):\n        """\n        :type n_rows: int\n        :type n_cols: int\n        """\n        self.n_rows = n_rows\n        self.n_cols = n_cols\n        self.rs = ReservoirSampling(n_rows * n_cols)\n\n    def flip(self):\n        """\n        :rtype: List[int]\n        """\n        n = self.rs.get_next()\n        return self.n2rc(n)\n\n    def n2rc(self, n):\n        r = n // self.n_cols\n        c = n - r * self.n_cols\n        return [r, c]\n\n    def reset(self):\n        """\n        :rtype: void\n        """\n        self.rs.reset()\n\n\n# Your Solution object will be instantiated and called as such:\n# obj = Solution(n_rows, n_cols)\n# param_1 = obj.flip()\n# obj.reset()\n```
[]