LeetCode 519: Random Flip Matrix

Problem Restatement

We are given a binary matrix with:

m rows
n columns

Initially, every cell contains:

0

We need to design a data structure supporting two operations.

Operations

flip()

Randomly choose one remaining cell containing 0.

Change it to:

1

Return its coordinates.

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

reset()

Set all cells back to:

0

The official problem asks us to randomly flip zero cells without repeating already flipped positions, while supporting reset efficiently. (leetcode.com)

Input and Output

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

Examples

Example:

solution = Solution(2, 3)

The matrix is:

0 0 0
0 0 0

Suppose:

solution.flip()

returns:

[0, 1]

Now the matrix becomes:

0 1 0
0 0 0

If another call returns:

[1, 2]

then:

0 1 0
0 0 1

After:

solution.reset()

the matrix returns to:

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:

O(1)

per operation.

Key Insight

Treat the matrix as a flat array.

For example:

m = 2
n = 3

The cells correspond to:

Now the problem becomes:

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:

remaining = 6

meaning indices [0, 5] are still available.

We randomly choose:

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:

Initially:

remaining = m * n

During flip():

1. Randomly choose:

   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:

   remaining = rows * cols

Correctness

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

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

Here:

The hash map stores only modified positions.

Implementation

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:

self.remaining = m * n

Initially, every flat index is available.

The hash map stores virtual swaps:

self.mapping = {}

Choose a random available position:

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

Get the actual value represented by r:

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

If r was never swapped, it represents itself.

Find the value currently represented by the last available slot:

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

Store the virtual swap:

self.mapping[r] = last

Shrink the available range:

self.remaining -= 1

Convert the flat index into coordinates:

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

During reset:

self.mapping.clear()

removes all virtual swaps.

Testing

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: