RandomFlipMatrix519.java

/**
 * 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.
 */

public class RandomFlipMatrix519 {
    /**
     * https://leetcode.com/problems/random-flip-matrix/discuss/154053/Java-AC-Solution-call-Least-times-of-Random.nextInt()-function
     */
    class Solution {
        private Map<Integer, Integer> map = new HashMap<>();
        private int size;
        private int N;
        private int nCols;
        private Random rand = new Random();
    
        public Solution(int n_rows, int n_cols) {
            this.N = n_rows * n_cols;
            this.nCols = n_cols;
            this.size = this.N;        
        }
        
        public int[] flip() {
            int idx = rand.nextInt(this.size--);
            int val = map.getOrDefault(idx, idx);
            map.put(idx, map.getOrDefault(this.size, this.size));
            return new int[]{val / this.nCols, val % this.nCols};
        }
        
        public void reset() {
            map.clear();
            this.size = this.N;
        }
    }
    

    class Solution2 {
        private int N;
        private int nCols;
        private Random rand = new Random();
        private Set<Integer> set = new HashSet<>();
    
        public Solution(int n_rows, int n_cols) {
            this.N = n_rows * n_cols;
            this.nCols = n_cols;
            // this.size = this.N;        
        }
        
        public int[] flip() {
            int val = rand.nextInt(this.N);
            while (set.contains(val)) {
                val = rand.nextInt(this.N);
            }
            set.add(val);
            return new int[]{val / this.nCols, val % this.nCols};
        }
        
        public void reset() {
            this.set.clear();
        }
    }


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


}