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 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows and 0 <= col.id < n_cols
flip will not be called when the matrix has no 0 values left.
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_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren't any.

Companies:
Google

Related Topics:
Random

Solution 1.

// 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;
    }
};

Solution 2.

Same idea as Solution 1, but use unordered_map to save space, and time if we only flip a small set of the points.

// OJ: https://leetcode.com/problems/random-flip-matrix/
// Time:
//   Solution: O(1)
//   flip: O(1)
//   reset: O(MN) in worst case
// Space: O(MN) in worst case
// Ref: https://leetcode.com/problems/random-flip-matrix/solution/
class Solution {
private:
    unordered_map<int, int> m;
    int size, M, N;
    //c++11 random integer generation
    mt19937 rng{random_device{}()};
    //uniform random integer in [0, bound]
    int randint(int bound) {
        uniform_int_distribution<int> uni(0, bound);
        return uni(rng);
    }
public:
    Solution(int M, int N): M(M), N(N), size(M * N) {}
    
    vector<int> flip() {
        int r = randint(--size);
        int x = m.count(r) ? m[r] : r;
        m[r] = m.count(size) ? m[size] : size;
        return { x / N, x % N };
    }
    
    void reset() {
        m.clear();
        size = M * N;
    }
};

Java

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

// 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(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)
        self.fliped.add(pos)
        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()

519 - Random Flip Matrix

519. Random Flip Matrix (Medium)

Solution 1.

Solution 2.

All Problems

All Solutions