#519

Random Flip Matrix

specialist · 960 · lc medium +32 · 45.5% accepted · 461 likes · top 29%

Description

An m x n binary matrix starts with all zeros. Design a class that uniformly at random selects a zero-valued cell, flips it to 1, and returns its index. Minimize calls to the language's built-in random generator.

Implement the Solution class:

- Solution(int m, int n) initializes the matrix with dimensions m and n.

- int[] flip() picks a uniformly random cell [i, j] with value 0, sets it to 1, and returns [i, j].

- void reset() resets every cell back to 0.

Example 1:

Input

["Solution", "flip", "flip", "flip", "reset", "flip"]

[[3, 1], [], [], [], [], []]

Output

[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

Example 2:

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.

Code

class Solution:

    def __init__(self, m: int, n: int):
        

    def flip(self) -> List[int]:
        

    def reset(self) -> None:
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(m, n)
# param_1 = obj.flip()
# obj.reset()

class Solution:

    def __init__(self, m: int, n: int):
        

    def flip(self) -> List[int]:
        

    def reset(self) -> None:
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(m, n)
# param_1 = obj.flip()
# obj.reset()