Abstract / Summary

Generate a random binary matrix of given size with the same row and column flip probabilities as a given matrix.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 46% (60k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• Math
• Randomized
• Reservoir Sampling

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class models a random selection process over a rectangular grid of size m × n. Each call to flip returns a unique cell coordinate until a reset is invoked, after which the selection pool is cleared. The implementation mixes deterministic bookkeeping with stochastic sampling to maintain uniqueness while minimizing overhead.

Initialization

When an instance is created, the constructor stores the dimensions, computes the total number of cells, and delegates to reset to establish the initial state.

def __init__(self, m: int, n: int):
    self.m = m
    self.n = n
    self.limit = m * n
    self.reset()

The limit field represents the cardinality of the selection space and is used throughout the class to bound random draws.

Reset

reset reinitializes the internal containers that track used and available positions. The avoid set records coordinates that have already been emitted, while available holds a pool of pre-computed coordinates that can be drawn without further randomness.

def reset(self) -> None:
    self.avoid = set()
    self.available = []

By clearing both structures, the class returns to a pristine state where every cell is eligible for selection again.

Helper for Coordinate Conversion

The private method two translates a linear index into a pair of row and column indices using integer division and remainder. This conversion is central to mapping the random integer space onto the two-dimensional grid.

def two(self, i):
    return ( i % self.m, i // self.m )

Because the modulus uses self.m, the method yields coordinates in the order (column, row), matching the expected output format.

Flip Logic

The core of the class resides in flip. The method first checks whether the available list contains pre-computed coordinates. If it does, the last element is removed and returned, which avoids the cost of a random number generation and a membership test.

if self.available:
    result = self.available[-1]
    del self.available[-1]

When available is empty, the method resorts to random sampling over the full index range [0, self.limit - 1]. The sampled index is converted to a coordinate via two. If the resulting coordinate already appears in avoid, the loop repeats until a fresh coordinate is found.

else:
    result = self.two(randint(0, self.limit - 1))
    while result in self.avoid:
        result = self.two(randint(0, self.limit - 1))

After a coordinate is selected, it is recorded in avoid to guarantee future uniqueness.

self.avoid.add(result)

A crucial edge-case handling step follows: when the available list is empty and the number of avoided coordinates reaches at least half of the total cells, the method repopulates available with every coordinate that has not yet been avoided. This bulk construction reduces the expected number of random draws as the pool of free cells shrinks. The newly built list is shuffled to preserve randomness for subsequent draws.

if not self.available and len(self.avoid) * 2 >= self.limit:
    for i in range(self.limit):
        if self.two(i) not in self.avoid:
            self.available.append(self.two(i))
    shuffle(self.available)

Finally, the selected coordinate is returned to the caller.

return result

Edge Cases Handled

The implementation gracefully manages the situation where the pool of remaining cells becomes small. By switching from on-the-fly random sampling to a pre-computed list once the avoided set occupies at least half of the space, the algorithm avoids the pathological case where repeated random draws repeatedly hit already-used cells.

When the grid contains only a single cell (m = 1 and n = 1), the first call to flip draws that cell directly from the available list after it is populated during the first repopulation step. Subsequent calls will always return the same coordinate until reset clears the state.

If flip is invoked after all cells have been exhausted, the available list will contain the last remaining coordinate, ensuring that the method still returns a valid result without entering an infinite loop.

Performance Optimizations

The code leverages a set (avoid) for constant-time membership checks, which is essential when repeatedly testing whether a randomly generated coordinate has already been emitted.

By storing pre-computed coordinates in a list (available) and popping from the end, the implementation benefits from O(1) removal without the overhead of shifting elements.

The conditional bulk construction of available only when the avoided set reaches a threshold reduces the expected number of random draws, especially in the later stages of the selection process where collisions become frequent.

Shuffling the available list once after it is built ensures that subsequent draws remain uniformly random without incurring per-draw shuffling costs.

Overall, the design balances lazy random sampling with deterministic batch preparation to keep the average work per flip call low throughout the lifecycle of the object.

Imagine a giant grid filled with many empty spots. This computer code acts like a helper that picks one of those spots for you.

When the helper gets asked to pick a spot, it first checks if there are already some spots kept on a special list. If the list has spots waiting, the helper just grabs the last one from there. If the list is empty, the helper starts randomly guessing spots on the grid. It keeps picking a spot until it finds one that has not been chosen before.

Once a spot is chosen, the helper remembers it so that it never picks the same one again. After enough spots are picked and forgotten, the helper sometimes pauses to look at the whole grid. It finds all the spots that have not been picked yet and adds them to that special list so they are ready for next time. Finally, the reset action clears out all the memories of which spots were picked so the whole game can begin again from the start.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Python	Java			TS
	WalkCCC	C++				Java
	leetcode.ca				Python	Java
	LeetcodeHelp	C++			Python	Java
	Progiez	C++			Python	Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	halfrost						Go
	JoshCrozier		JS
	lkwq007				Python
	lzl124631x	C++
	ruoru			Rust
	suxrobGM							C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality