# Random Flip Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/random-flip-matrix)
Canonical: https://scaleengineer.com/dsa/problems/random-flip-matrix
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Algorithms:** [Reservoir Sampling](https://scaleengineer.com/algorithms/reservoir-sampling)
**Data structures:** Hash Table
---
## Problem
There is an `m x n` binary grid `matrix` with all the values set `0` initially. Design an algorithm to randomly pick an index `(i, j)` where `matrix[i][j] == 0` and flips it to `1`. All the indices `(i, j)` where `matrix[i][j] == 0` should be equally likely to be returned.

Optimize your algorithm to minimize the number of calls made to the **built-in** random function of your language and optimize the time and space complexity.

Implement the `Solution` class:

* `Solution(int m, int n)` Initializes the object with the size of the binary matrix `m` and `n`.
* `int[] flip()` Returns a random index `[i, j]` of the matrix where `matrix[i][j] == 0` and flips it to `1`.
* `void reset()` Resets all the values of the matrix to be `0`.

**Example 1:**

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

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

**Constraints:**

* `1 <= m, n <= 104`
* There will be at least one free cell for each call to `flip`.
* At most `1000` calls will be made to `flip` and `reset`.

# Approaches
## Brute Force with In-Memory Matrix
This approach directly simulates the problem description by maintaining a full `m x n` matrix in memory. Each cell in the matrix stores a boolean value indicating whether it has been flipped or not. When `flip()` is called, the algorithm repeatedly generates random `(row, col)` coordinates until it finds a cell that has not yet been flipped. This method is known as **Rejection Sampling**.
**Time:** *   **Constructor**: `O(m * n)` to initialize the matrix.
*   **`flip()`**: `O(1)` in the best case (first pick is valid), but the expected time is `O(N / (N - k))` where `N = m * n` and `k` is the number of flipped cells. This becomes very slow as `k` approaches `N`.
*   **`reset()`**: `O(m * n)` to re-initialize the matrix. · **Space:** O(m * n) to store the entire matrix.
**Pros:** **Simplicity**: The logic is very easy to understand and implement.
**Cons:** **High Space Complexity**: The `O(m * n)` space requirement is prohibitive for the given constraints (`m, n <= 10^4`), potentially causing Memory Limit Exceeded errors.; **Inefficient `flip()`**: The time complexity of `flip()` degrades as more cells are flipped. When the matrix is nearly full, finding the last few available cells can take a very long time due to repeated random picks landing on already flipped cells.; **Slow `reset()`**: Resetting the entire matrix takes `O(m * n)` time, which is inefficient.
### Explanation
The core idea is to keep a complete representation of the grid. The `Solution` class holds an `m x n` boolean array, say `flipped`, initialized to all `false`.

For the `flip()` operation, we generate random row and column indices. We then check `flipped[row][col]`. If it's `false`, we've found an available cell. We set `flipped[row][col]` to `true` and return `[row, col]`. If it's `true`, we reject this sample and repeat the process until an unflipped cell is found. Since the problem guarantees at least one cell is available, this loop will eventually terminate.

The `reset()` operation is straightforward: it re-initializes the `flipped` matrix to its original all-`false` state.

```java
import java.util.Random;

class Solution {
    private boolean[][] flipped;
    private int m;
    private int n;
    private Random rand;

    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
        this.rand = new Random();
        this.flipped = new boolean[m][n];
    }
    
    public int[] flip() {
        while (true) {
            int r = rand.nextInt(m);
            int c = rand.nextInt(n);
            if (!flipped[r][c]) {
                flipped[r][c] = true;
                return new int[]{r, c};
            }
        }
    }
    
    public void reset() {
        this.flipped = new boolean[m][n];
    }
}
```
### Algorithm
*   **Constructor `Solution(m, n)`**:
    1.  Initialize an `m x n` matrix (e.g., `boolean[][] flipped`) with all values `false`.
    2.  Store the dimensions `m` and `n`.
    3.  Initialize a random number generator.
*   **`flip()` Method**:
    1.  Start an infinite loop (or a `do-while` loop).
    2.  Generate a random row `r` within `[0, m-1]`.
    3.  Generate a random column `c` within `[0, n-1]`.
    4.  Check the state of the cell `(r, c)` in the `flipped` matrix.
    5.  If `flipped[r][c]` is `false`, it means the cell is available.
        a.  Mark it as flipped: `flipped[r][c] = true`.
        b.  Return the coordinates `[r, c]`.
        c.  Exit the loop.
    6.  If `flipped[r][c]` is `true`, the cell has already been picked. The loop continues to find another random cell.
*   **`reset()` Method**:
    1.  Create a new `m x n` matrix and set all its values to `false`, effectively resetting the state.

## Hash Map Remapping
This optimal approach avoids the high memory cost of a full matrix by recognizing that the number of `flip` calls is small. It treats the `m x n` grid as a virtual 1D array of size `total = m * n`. The core idea is to maintain a pool of available indices, which initially contains all indices from `0` to `total - 1`.

When `flip()` is called, we pick a random index from the available pool. To avoid picking it again, we virtually swap this picked index with the last index in the pool and then shrink the pool's size by one. A `HashMap` is used to efficiently track these swaps, storing only the indices that have been involved in a swap. This avoids allocating memory for all `m * n` cells.
**Time:** *   **Constructor**: `O(1)`.
*   **`flip()`**: `O(1)` on average, due to the constant-time performance of hash map operations.
*   **`reset()`**: `O(1)` as it only reinitializes a few variables and creates a new map. · **Space:** O(K), where K is the number of calls to `flip()`. Since K is at most 1000, this is very efficient.
**Pros:** **Optimal Space Complexity**: Space is `O(K)` where `K` is the number of flips, which is independent of the matrix size.; **Optimal Time Complexity**: `flip()` runs in `O(1)` average time.; **Fast Initialization and Reset**: The constructor and `reset()` methods are also `O(1)` (ignoring garbage collection of the old map).
**Cons:** **Conceptual Complexity**: The logic of virtual swapping using a hash map is less intuitive than a direct simulation.
### Explanation
We map each 2D coordinate `(i, j)` to a unique 1D index `k = i * n + j`. We maintain a variable, `top`, which represents the number of available (un-flipped) cells, initialized to `m * n`.

In `flip()`, we generate a random number `rand_idx` from `[0, top - 1]`. This `rand_idx` represents the k-th available element, not necessarily the cell with index `k`. We use a `HashMap` to resolve this. The map stores indices that have been picked and maps them to the values they were swapped with.

1.  Pick a random index `rand_idx` from the current valid range `[0, top - 1]`.
2.  The actual cell index we return, `result_idx`, is `map.getOrDefault(rand_idx, rand_idx)`. This gives us the true value at that position in our virtual array.
3.  We then shrink the valid range by decrementing `top`. To ensure `rand_idx` is not picked again, we virtually place the value from the end of the range (`top`) into the `rand_idx` position. We do this by updating the map: `map.put(rand_idx, map.getOrDefault(top, top))`. This means if `rand_idx` is ever generated again, we will instead use the value that was at the end of the pool.

This ensures each `flip()` is an `O(1)` operation on average, and the space used is proportional only to the number of flips performed.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

class Solution {
    private Map<Integer, Integer> map;
    private int m, n, top;
    private Random rand;

    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
        this.rand = new Random();
        reset();
    }
    
    public int[] flip() {
        // Generate a random index from the available range [0, top-1]
        int rand_idx = rand.nextInt(top);
        
        // The number of available cells decreases by one for the next call
        top--;
        
        // Get the actual cell index to return.
        // If rand_idx is in the map, it means its original value was swapped.
        // We use the mapped value. Otherwise, it hasn't been touched, so we use rand_idx itself.
        int result_idx = map.getOrDefault(rand_idx, rand_idx);
        
        // Now, we virtually "swap" the element at rand_idx with the element at the end of the available range (top).
        // Get the value that is currently at the `top` position.
        int top_val = map.getOrDefault(top, top);
        
        // Place the value from the end (`top_val`) into the `rand_idx` position for future picks.
        map.put(rand_idx, top_val);
        
        // Convert the 1D result index back to 2D coordinates
        return new int[]{result_idx / n, result_idx % n};
    }
    
    public void reset() {
        this.map = new HashMap<>();
        this.top = m * n;
    }
}
```
### Algorithm
*   **Conceptual Model**: Imagine a 1D array of all cell indices from `0` to `m*n - 1`. We need to randomly pick an index from this array without replacement.
*   **Data Structures**:
    *   `top`: An integer representing the count of available cells. Initially `m * n`.
    *   `map`: A `HashMap<Integer, Integer>` to store mappings for swapped indices.
*   **Constructor `Solution(m, n)`**:
    1.  Store `m` and `n`.
    2.  Call `reset()` to initialize `top` and the `map`.
*   **`flip()` Method**:
    1.  Generate a random index `rand_idx` in the range `[0, top - 1]`. `top` represents the size of the pool of available indices.
    2.  Decrement `top` to shrink the pool for the next call.
    3.  Determine the actual cell index to return. If `rand_idx` is a key in our `map`, it means its original value was swapped. We use the mapped value: `result_idx = map.get(rand_idx)`. Otherwise, `rand_idx` has not been touched, so `result_idx = rand_idx`.
    4.  To virtually "remove" `rand_idx` from the pool, we swap it with the last element of the pool, which is at index `top`. We find the value at index `top` (which could also have been swapped) using `top_val = map.getOrDefault(top, top)`.
    5.  Update the map to reflect the swap: `map.put(rand_idx, top_val)`. This ensures that if `rand_idx` is picked again, we will use `top_val` instead.
    6.  Convert the 1D `result_idx` back to 2D coordinates `[result_idx / n, result_idx % n]` and return them.
*   **`reset()` Method**:
    1.  Reset `top` to `m * n`.
    2.  Clear the `map` by creating a new empty `HashMap`.

# Solutions
### Java

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

```

### Python

```python
class Solution:
    # Your Solution object will be instantiated and called as such: # obj = Solution(m, n) # param_1 = obj.flip() # obj.reset()
    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()

```