LeetCode 519 - Random Flip Matrix

Difficulty: 🟡 Medium
Topics: Hash Table, Math, Reservoir Sampling, Randomized

Solution

Problem Understanding

The problem gives us an m x n matrix where every cell initially contains 0. We need to design a data structure that supports two operations efficiently:

flip()

This operation must randomly choose one of the remaining cells that still contains 0, return its coordinates [row, col], and then change that cell to 1. 2. reset()

This operation restores the entire matrix back to all zeros.

The important requirement is that every unflipped cell must have an equal probability of being selected. In other words, if there are currently k available cells, each one must be chosen with probability 1 / k.

The matrix dimensions can be very large. Since both m and n can be up to 10^4, the total number of cells can be as large as:

10^4 * 10^4 = 10^8

A matrix with one hundred million cells is too large to explicitly store in memory if we try to maintain the entire grid.

However, the problem also tells us something very important:

There will be at most 1000 calls to flip() and reset() combined.

This changes the nature of the problem completely. Even though the matrix may be huge, the number of operations is very small. That strongly suggests we should only store information about the cells that have actually been flipped, instead of storing the entire matrix.

Another key detail is that the problem explicitly asks us to minimize calls to the built in random function. That means repeatedly generating random coordinates until we find an unused one is not ideal, especially when the matrix becomes nearly full.

Some important edge cases include:

A matrix with only one cell, such as 1 x 1
Calling flip() repeatedly until only one unflipped cell remains
Large matrices like 10000 x 10000
Calling reset() after several flips
Ensuring uniform randomness even after many flips

The problem guarantees that every call to flip() will always have at least one remaining zero cell available.

Approaches

Brute Force Approach

The most straightforward solution is to explicitly store the entire matrix and repeatedly choose random coordinates until we find a cell that still contains 0.

For example:

Generate a random row and column.
Check whether that position is still 0.
If it is already 1, try again.
Otherwise, mark it as 1 and return it.

This approach is correct because every valid cell can eventually be selected. However, it becomes increasingly inefficient as more cells are flipped.

Suppose the matrix is almost full and only one zero remains. The probability of randomly hitting that last zero becomes extremely small, which means we may need many repeated random attempts before success.

The memory usage is also problematic. A full matrix of size 10^8 is far too large to store efficiently.

Optimal Approach

The key insight is that we do not actually need to store the entire matrix.

Instead, we can think of the matrix as a flattened array of indices:

0, 1, 2, 3, ..., m*n - 1

Each index maps to a matrix coordinate:

row = index // n
col = index % n

Now the problem becomes:

Randomly select an unused number from a range without repetition.

This is very similar to performing a partial Fisher-Yates shuffle.

We maintain:

remaining, the number of still-available cells
A hash map that stores remapped indices

When we choose a random index r in [0, remaining - 1], we:

Determine the actual value associated with r
Move the last available value into position r
Decrease remaining

This simulates removing a random element from a shrinking pool without storing the entire array.

Because we only store modified mappings, the memory usage remains proportional to the number of flips, not the matrix size.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Worst case O(k) per flip	O(m × n)	Repeated random retries become expensive when matrix fills up
Optimal	O(1) average per flip	O(k)	Uses hash map to simulate Fisher-Yates shuffle lazily

Here, k is the number of performed flips.

Algorithm Walkthrough

Step 1: Flatten the Matrix

Instead of treating the matrix as two dimensional, treat it as a one dimensional array of size:

total = m * n

Each integer corresponds to one matrix cell.

For example, in a 3 x 2 matrix:

Index	Coordinate
0	(0,0)
1	(0,1)
2	(1,0)
3	(1,1)
4	(2,0)
5	(2,1)

This allows us to work with a simple integer range.

Step 2: Maintain Remaining Available Cells

Keep a variable:

remaining = total

At any moment, the valid selectable indices are:

[0, remaining - 1]

After each flip, the available range shrinks by one.

Step 3: Randomly Select an Index

Generate:

r = random integer in [0, remaining - 1]

This guarantees uniform selection among all remaining cells.

Step 4: Resolve the Actual Value

We use a hash map called mapping.

If r has been remapped previously, use:

actual = mapping[r]

Otherwise:

actual = r

This simulates a dynamically shuffled array without explicitly storing it.

Step 5: Swap With the Last Available Position

The last available index is:

remaining - 1

We move its value into position r.

Again, if the last index has already been remapped, use that mapped value.

Conceptually:

mapping[r] = value_at_last_position

Then decrement:

remaining -= 1

This effectively removes the selected value from future consideration.

Step 6: Convert Back to Matrix Coordinates

Once we obtain the flattened index actual, convert it back:

row = actual // n
col = actual % n

Return:

[row, col]

Step 7: Reset

To reset the matrix:

Clear the hash map
Restore remaining = total

This instantly resets the structure without rebuilding a giant matrix.

Why it works

The algorithm maintains the invariant that the selectable range [0, remaining - 1] always represents all currently available cells exactly once.

Each flip() chooses uniformly from this range. The hash map lazily simulates swapping the chosen element with the last available element, exactly like Fisher-Yates shuffle.

Because every remaining cell occupies one unique position in the selectable range, every unflipped cell has equal probability of being chosen.

Python Solution

from typing import List
import random

class Solution:

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

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

        actual_index = self.mapping.get(random_index, random_index)

        last_index = self.remaining - 1
        self.mapping[random_index] = self.mapping.get(last_index, last_index)

        self.remaining -= 1

        row = actual_index // self.cols
        col = actual_index % self.cols

        return [row, col]

    def reset(self) -> None:
        self.mapping.clear()
        self.remaining = self.total

# Your Solution object will be instantiated and called as such:
# obj = Solution(m, n)
# param_1 = obj.flip()
# obj.reset()

The constructor initializes the matrix dimensions and computes the total number of cells. Instead of allocating the entire matrix, it stores only a hash map and a counter representing how many cells remain available.

The flip() method first selects a random position inside the remaining available range. Since some positions may have been remapped during earlier operations, the hash map is checked to determine the true value currently stored at that position.

The selected value is then removed from future consideration by replacing it with the value from the last available position. This is the same idea used in Fisher-Yates shuffle.

Finally, the flattened index is converted back into two dimensional coordinates using integer division and modulo operations.

The reset() method clears all remappings and restores the full available range instantly.

Go Solution

package main

import (
	"math/rand"
)

type Solution struct {
	rows      int
	cols      int
	total     int
	remaining int
	mapping   map[int]int
}

func Constructor(m int, n int) Solution {
	total := m * n

	return Solution{
		rows:      m,
		cols:      n,
		total:     total,
		remaining: total,
		mapping:   make(map[int]int),
	}
}

func (this *Solution) Flip() []int {
	randomIndex := rand.Intn(this.remaining)

	actualIndex, exists := this.mapping[randomIndex]
	if !exists {
		actualIndex = randomIndex
	}

	lastIndex := this.remaining - 1

	lastValue, exists := this.mapping[lastIndex]
	if !exists {
		lastValue = lastIndex
	}

	this.mapping[randomIndex] = lastValue

	this.remaining--

	row := actualIndex / this.cols
	col := actualIndex % this.cols

	return []int{row, col}
}

func (this *Solution) Reset() {
	this.mapping = make(map[int]int)
	this.remaining = this.total
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(m, n);
 * param_1 := obj.Flip();
 * obj.Reset();
 */

The Go implementation follows the same algorithm as the Python version. The primary difference is explicit handling of map lookups using the value, exists pattern.

Go uses rand.Intn(this.remaining) to generate a random number in the desired range. Slices are used for returning coordinates.

Since Go maps do not have a direct clear() method, reset creates a brand new map instead.

Worked Examples

Example 1

Input:
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3,1], [], [], [], [], []]

The matrix contains 3 cells total.

Initial flattened representation:

Index	Coordinate
0	(0,0)
1	(1,0)
2	(2,0)

Initial state:

Variable	Value
remaining	3
mapping	{}

Suppose the first random choice is 1.

First flip()

Action	Result
random_index	1
actual_index	1
last_index	2
mapping[1] = 2	mapping becomes {1: 2}
remaining	2

Returned coordinate:

1 // 1 = 1
1 % 1 = 0

Return:

[1, 0]

Remaining available values now behave like:

[0, 2]

Second flip()

Suppose random choice is 1.

Action	Result
random_index	1
actual_index	mapping[1] = 2
last_index	1
mapping[1] = mapping[1] = 2	unchanged
remaining	1

Return:

[2, 0]

Remaining available value:

[0]

Third flip()

Only one value remains.

Action	Result
random_index	0
actual_index	0
last_index	0
remaining	0

Return:

[0, 0]

reset()

Variable	Value
mapping	{}
remaining	3

All cells become available again.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) average per operation	Hash map lookups and updates are constant time on average
Space	O(k)	Only flipped positions are stored in the hash map

The algorithm avoids storing the entire matrix. Instead, it only stores remapped indices created during flips.

If k flips have occurred, at most k entries exist in the hash map. Since the problem limits total operations to 1000, the memory usage remains very small even for enormous matrices.

Test Cases

from typing import List
import random

class Solution:

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

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

        actual_index = self.mapping.get(random_index, random_index)

        last_index = self.remaining - 1
        self.mapping[random_index] = self.mapping.get(last_index, last_index)

        self.remaining -= 1

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

    def reset(self) -> None:
        self.mapping.clear()
        self.remaining = self.total

# Basic functionality test
obj = Solution(3, 1)
results = {tuple(obj.flip()) for _ in range(3)}
assert results == {(0, 0), (1, 0), (2, 0)}  # all cells returned exactly once

# Reset functionality
obj.reset()
cell = obj.flip()
assert cell in [[0, 0], [1, 0], [2, 0]]  # all cells available again after reset

# Single cell matrix
obj = Solution(1, 1)
assert obj.flip() == [0, 0]  # only possible cell

# Two by two matrix uniqueness
obj = Solution(2, 2)
seen = set()

for _ in range(4):
    cell = tuple(obj.flip())
    assert cell not in seen  # no duplicate flips
    seen.add(cell)

assert len(seen) == 4  # all cells visited

# Large dimensions
obj = Solution(10000, 10000)
cell = obj.flip()

assert 0 <= cell[0] < 10000  # valid row
assert 0 <= cell[1] < 10000  # valid column

# Multiple resets
obj = Solution(2, 2)

for _ in range(3):
    visited = set()

    for _ in range(4):
        visited.add(tuple(obj.flip()))

    assert len(visited) == 4  # all cells reachable
    obj.reset()

# Remaining single element case
obj = Solution(1, 3)

first = tuple(obj.flip())
second = tuple(obj.flip())
third = tuple(obj.flip())

assert len({first, second, third}) == 3  # final remaining element handled correctly

Test	Why
3x1 example	Verifies standard functionality
Reset test	Ensures reset restores all cells
1x1 matrix	Smallest possible input
2x2 uniqueness	Confirms no duplicate selections
10000x10000 matrix	Verifies scalability without full matrix allocation
Multiple resets	Ensures state is fully cleared repeatedly
Final remaining cell	Tests behavior when only one option remains

Edge Cases

Single Cell Matrix

A 1 x 1 matrix is the smallest possible input. After one flip(), there are no remaining cells.

This case can expose off by one errors in random index generation or remaining count management. The implementation handles this correctly because random.randint(0, 0) is valid and the remaining count decreases cleanly from 1 to 0.

Nearly Full Matrix

When only one cell remains unflipped, naive retry based solutions become extremely inefficient because they repeatedly hit already used cells.

The hash map based solution avoids retries entirely. The selectable range always shrinks exactly to the number of remaining cells, so selecting the final cell is still an O(1) operation.

Very Large Matrix Dimensions

A matrix such as 10000 x 10000 contains one hundred million cells. Explicitly allocating such a matrix would consume enormous memory.

The implementation never stores the full matrix. It only stores remapped entries corresponding to performed flips, making the memory usage proportional to the number of operations rather than matrix size.

Reset After Multiple Flips

Resetting after several flips could easily leave stale state behind if mappings are not fully cleared.

The implementation solves this by clearing the hash map completely and restoring the remaining counter to the original total number of cells. This guarantees the matrix behaves exactly like a fresh instance after reset.