##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/519.html

# 519. Random Flip Matrix (Medium)

You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system's Math.random() and optimize the time and space complexity.

Note:

1. 1 <= n_rows, n_cols <= 10000
2. 0 <= row.id < n_rows and 0 <= col.id < n_cols
3. flip will not be called when the matrix has no 0 values left.
4. the total number of calls to flip and reset will not exceed 1000.

Example 1:

Input:
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]


Example 2:

Input:
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, n_rows and n_colsflip and reset have no arguments. Arguments are always wrapped with a list, even if there aren't any.

Companies:

Related Topics:
Random

## Solution 1.

• class Solution {
int n_rows;
int n_cols;
int remaining;
Map<Integer, Integer> map;
Random random;

public Solution(int n_rows, int n_cols) {
this.n_rows = n_rows;
this.n_cols = n_cols;
remaining = n_rows * n_cols;
map = new HashMap<Integer, Integer>();
random = new Random();
}

public int[] flip() {
int randNum = random.nextInt(remaining);
remaining--;
int index = map.getOrDefault(randNum, randNum);
int value = map.getOrDefault(remaining, remaining);
map.put(randNum, value);
int[] rowColumn = {index / n_cols, index % n_cols};
return rowColumn;
}

public void reset() {
map.clear();
remaining = n_rows * n_cols;
}
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(n_rows, n_cols);
* int[] param_1 = obj.flip();
* obj.reset();
*/
############

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();
*/

• // OJ: https://leetcode.com/problems/random-flip-matrix/
// Time:
//   Solution: O(MN)
//   flip: O(1)
//   reset: O(1)
// Space: O(MN)
class Solution {
private:
vector<int> v;
int size, M, N;
public:
Solution(int M, int N): M(M), N(N), size(M * N), v(M * N) {
for (int i = 0; i < size; ++i) v[i] = i;
srand(time(NULL));
}

vector<int> flip() {
swap(v[rand() % size], v[size - 1]);
--size;
return { v[size] / N, v[size] % N };
}

void reset() {
size = M * N;
}
};

• 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()

############

class Solution(object):

def __init__(self, n_rows, n_cols):
"""
:type n_rows: int
:type n_cols: int
"""
self.M = n_rows
self.N = n_cols
self.total = self.M * self.N
self.fliped = set()

def flip(self):
"""
:rtype: List[int]
"""
pos = random.randint(0, self.total - 1)
while pos in self.fliped:
pos = random.randint(0, self.total - 1)
return [pos / self.N, pos % self.N]

def reset(self):
"""
:rtype: void
"""
self.fliped.clear()

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