# LeetCode 519: Random Flip Matrix

## Problem Restatement

We are given a binary matrix with:

```text
m rows
n columns
```

Initially, every cell contains:

```text
0
```

We need to design a data structure supporting two operations.

## Operations

### `flip()`

Randomly choose one remaining cell containing `0`.

Change it to:

```text
1
```

Return its coordinates.

Every remaining zero cell must have equal probability of being chosen.

### `reset()`

Set all cells back to:

```text
0
```

The official problem asks us to randomly flip zero cells without repeating already flipped positions, while supporting reset efficiently. ([leetcode.com](https://leetcode.com/problems/random-flip-matrix/?utm_source=chatgpt.com))

## Input and Output

| Method | Meaning |
|---|---|
| `Solution(m, n)` | Initialize the matrix |
| `flip()` | Randomly flip one zero cell |
| `reset()` | Restore all cells to zero |

The matrix can be large, so explicitly storing every cell is inefficient.

## Examples

Example:

```python
solution = Solution(2, 3)
```

The matrix is:

```text
0 0 0
0 0 0
```

Suppose:

```python
solution.flip()
```

returns:

```python
[0, 1]
```

Now the matrix becomes:

```text
0 1 0
0 0 0
```

If another call returns:

```python
[1, 2]
```

then:

```text
0 1 0
0 0 1
```

After:

```python
solution.reset()
```

the matrix returns to:

```text
0 0 0
0 0 0
```

## First Thought: Store Every Zero Cell

A direct solution is:

1. Store every available cell in a list
2. Randomly choose one index
3. Remove that cell from the list

This works, but removal from the middle of a large list can be expensive.

Also, explicitly storing every coordinate uses large memory for big matrices.

We want something closer to:

```text
O(1)
```

per operation.

## Key Insight

Treat the matrix as a flat array.

For example:

```text
m = 2
n = 3
```

The cells correspond to:

| Flat index | Cell |
|---:|---|
| 0 | `(0, 0)` |
| 1 | `(0, 1)` |
| 2 | `(0, 2)` |
| 3 | `(1, 0)` |
| 4 | `(1, 1)` |
| 5 | `(1, 2)` |

Now the problem becomes:

```text
Randomly choose an unused integer from [0, size - 1]
```

without repetition.

This is similar to drawing random cards from a shuffled deck.

Instead of physically shuffling the whole array, we simulate swaps lazily using a hash map.

## Virtual Swapping Idea

Suppose:

```text
remaining = 6
```

meaning indices `[0, 5]` are still available.

We randomly choose:

```text
r = 2
```

We want to remove index `2` from future choices.

Conceptually:

1. Use the value currently stored at `2`
2. Move the last available value into position `2`
3. Decrease the available range

This is exactly the same idea as removing a random item from an array by swapping with the end.

But instead of storing the full array, we store only modified positions in a hash map.

## Algorithm

Store:

| Variable | Meaning |
|---|---|
| `rows` | Number of rows |
| `cols` | Number of columns |
| `remaining` | Number of unused cells |
| `mapping` | Virtual swap table |

Initially:

```python
remaining = m * n
```

During `flip()`:

1. Randomly choose:
   ```python
   r = random.randint(0, remaining - 1)
   ```
2. Find the actual value represented by `r`
3. Find the actual value represented by `remaining - 1`
4. Store the swap in the map
5. Decrease `remaining`
6. Convert the chosen flat index back into `(row, col)`

During `reset()`:

1. Clear the map
2. Restore:
   ```python
   remaining = rows * cols
   ```

## Correctness

At any moment, the available flat indices are conceptually the integers:

```text
0 to remaining - 1
```

The hash map simulates swaps between used and unused positions.

When `flip()` chooses a random integer `r` uniformly from this range, every remaining unused cell has equal probability of being selected.

The algorithm retrieves the actual cell index represented by `r`, accounting for any previous virtual swaps.

It then replaces `r` with the value currently represented by the last available position `remaining - 1`. This simulates removing the chosen element from the active range.

After decreasing `remaining`, the chosen cell can no longer be selected again.

Thus every flip returns a distinct zero cell with uniform probability among all remaining zero cells.

`reset()` clears all virtual swaps and restores the full available range, so all cells become available again.

Therefore the data structure behaves exactly as required.

## Complexity

| Operation | Time | Space |
|---|---|---|
| `flip()` | `O(1)` average | `O(k)` total |
| `reset()` | `O(1)` | `O(1)` extra |

Here:

| Symbol | Meaning |
|---|---|
| `k` | Number of flipped cells since last reset |

The hash map stores only modified positions.

## Implementation

```python
from typing import List
import random

class Solution:

    def __init__(self, m: int, n: int):
        self.rows = m
        self.cols = n
        self.remaining = m * n
        self.mapping = {}

    def flip(self) -> List[int]:
        r = random.randint(0, self.remaining - 1)

        actual = self.mapping.get(r, r)

        last = self.mapping.get(
            self.remaining - 1,
            self.remaining - 1,
        )

        self.mapping[r] = last

        self.remaining -= 1

        return [
            actual // self.cols,
            actual % self.cols,
        ]

    def reset(self) -> None:
        self.remaining = self.rows * self.cols
        self.mapping.clear()
```

## Code Explanation

Initialize the matrix state:

```python
self.remaining = m * n
```

Initially, every flat index is available.

The hash map stores virtual swaps:

```python
self.mapping = {}
```

Choose a random available position:

```python
r = random.randint(0, self.remaining - 1)
```

Get the actual value represented by `r`:

```python
actual = self.mapping.get(r, r)
```

If `r` was never swapped, it represents itself.

Find the value currently represented by the last available slot:

```python
last = self.mapping.get(
    self.remaining - 1,
    self.remaining - 1,
)
```

Store the virtual swap:

```python
self.mapping[r] = last
```

Shrink the available range:

```python
self.remaining -= 1
```

Convert the flat index into coordinates:

```python
[
    actual // self.cols,
    actual % self.cols,
]
```

During reset:

```python
self.mapping.clear()
```

removes all virtual swaps.

## Testing

```python
def test_random_flip_matrix():
    s = Solution(2, 2)

    seen = set()

    for _ in range(4):
        cell = tuple(s.flip())

        assert cell not in seen
        seen.add(cell)

    assert len(seen) == 4

    s.reset()

    seen_after_reset = set()

    for _ in range(4):
        cell = tuple(s.flip())

        assert cell not in seen_after_reset
        seen_after_reset.add(cell)

    assert len(seen_after_reset) == 4

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| Flip all cells once | Confirms no repetition |
| Reset after full usage | Confirms matrix restoration |
| Coordinate uniqueness | Ensures correct virtual swapping |
| Small matrix | Easy to manually verify |