Medium
Quiz
#519 Random Flip Matrix
APPROACH
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.
1 of 4
1:00
What is the optimal approach for this problem?