Welcome to Subscribe On Youtube
519. Random Flip Matrix
Description
There is an m x n
binary grid matrix
with all the values set 0
initially. Design an algorithm to randomly pick an index (i, j)
where matrix[i][j] == 0
and flips it to 1
. All the indices (i, j)
where matrix[i][j] == 0
should be equally likely to be returned.
Optimize your algorithm to minimize the number of calls made to the builtin random function of your language and optimize the time and space complexity.
Implement the Solution
class:
Solution(int m, int n)
Initializes the object with the size of the binary matrixm
andn
.int[] flip()
Returns a random index[i, j]
of the matrix wherematrix[i][j] == 0
and flips it to1
.void reset()
Resets all the values of the matrix to be0
.
Example 1:
Input ["Solution", "flip", "flip", "flip", "reset", "flip"] [[3, 1], [], [], [], [], []] Output [null, [1, 0], [2, 0], [0, 0], null, [2, 0]] Explanation Solution solution = new Solution(3, 1); solution.flip(); // return [1, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned. solution.flip(); // return [2, 0], Since [1,0] was returned, [2,0] and [0,0] solution.flip(); // return [0, 0], Based on the previously returned indices, only [0,0] can be returned. solution.reset(); // All the values are reset to 0 and can be returned. solution.flip(); // return [2, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned.
Constraints:
1 <= m, n <= 10^{4}
 There will be at least one free cell for each call to
flip
.  At most
1000
calls will be made toflip
andreset
.
Solutions

class Solution { private int m; private int n; private int total; private Random rand = new Random(); private Map<Integer, Integer> mp = new HashMap<>(); public Solution(int m, int n) { this.m = m; this.n = n; this.total = m * n; } public int[] flip() { int x = rand.nextInt(total); int idx = mp.getOrDefault(x, x); mp.put(x, mp.getOrDefault(total, total)); return new int[] {idx / n, idx % n}; } public void reset() { total = m * n; mp.clear(); } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(m, n); * int[] param_1 = obj.flip(); * obj.reset(); */

class Solution: def __init__(self, m: int, n: int): self.m = m self.n = n self.total = m * n self.mp = {} def flip(self) > List[int]: self.total = 1 x = random.randint(0, self.total) idx = self.mp.get(x, x) self.mp[x] = self.mp.get(self.total, self.total) return [idx // self.n, idx % self.n] def reset(self) > None: self.total = self.m * self.n self.mp.clear() # Your Solution object will be instantiated and called as such: # obj = Solution(m, n) # param_1 = obj.flip() # obj.reset()