# 519     Random Flip Matrix

## 519. [Random Flip Matrix](https://leetcode.com/problems/random-flip-matrix/description/)

## 1. Question

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](https://en.wikipedia.org/wiki/Discrete_uniform_distribution), 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_cols`. `flip` and`reset`have no arguments. Arguments are always wrapped with a list, even if there aren't any.

## 2. Implementation

(1) Fisher-Yate 算法

```java
class Solution {
    // 思路: Fisher-Yate的2D版本
    Map<Integer, Integer> map;
    Random rand;
    int rows, cols, total;

    public Solution(int n_rows, int n_cols) {
        map = new HashMap();
        rand = new Random();
        rows = n_rows;
        cols = n_cols;
        total = rows * cols;
    }

    public int[] flip() {
        int index = rand.nextInt(total--);
        // Check if we have put anything in this index
        int x = map.getOrDefault(index, index);
        // swap index with total
        map.put(index, map.getOrDefault(total, total));
        return new int[] {x / cols, x % cols};
    }

    public void reset() {
        map.clear();
        total = rows * 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();
 */
```

## 3. Time & Space Complexity

Fisher-Yate 时间复杂度flip: O(1), 空间复杂度O(m \* n), 空间主要是map，m为行，n为列


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/randomness/519-random-flip-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.