Random Flip Matrix

Med

#0504Time: * **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.

Patterns

Math Randomized

Algorithms

Reservoir Sampling

Data structures

Hash Table

Prompt

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 <= 10⁴
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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Random;2 3class Solution {4    private boolean[][] flipped;5    private int m;6    private int n;7    private Random rand;8 9    public Solution(int m, int n) {10        this.m = m;11        this.n = n;12        this.rand = new Random();13        this.flipped = new boolean[m][n];14    }15    16    public int[] flip() {17        while (true) {18            int r = rand.nextInt(m);19            int c = rand.nextInt(n);20            if (!flipped[r][c]) {21                flipped[r][c] = true;22                return new int[]{r, c};23            }24        }25    }26    27    public void reset() {28        this.flipped = new boolean[m][n];29    }30}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

Pick a random index rand_idx from the current valid range [0, top - 1].
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.
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.

1import java.util.HashMap;2import java.util.Map;3import java.util.Random;4 5class Solution {6    private Map<Integer, Integer> map;7    private int m, n, top;8    private Random rand;9 10    public Solution(int m, int n) {11        this.m = m;12        this.n = n;13        this.rand = new Random();14        reset();15    }16    17    public int[] flip() {18        // Generate a random index from the available range [0, top-1]19        int rand_idx = rand.nextInt(top);20        21        // The number of available cells decreases by one for the next call22        top--;23        24        // Get the actual cell index to return.25        // If rand_idx is in the map, it means its original value was swapped.26        // We use the mapped value. Otherwise, it hasn't been touched, so we use rand_idx itself.27        int result_idx = map.getOrDefault(rand_idx, rand_idx);28        29        // Now, we virtually "swap" the element at rand_idx with the element at the end of the available range (top).30        // Get the value that is currently at the `top` position.31        int top_val = map.getOrDefault(top, top);32        33        // Place the value from the end (`top_val`) into the `rand_idx` position for future picks.34        map.put(rand_idx, top_val);35        36        // Convert the 1D result index back to 2D coordinates37        return new int[]{result_idx / n, result_idx % n};38    }39    40    public void reset() {41        this.map = new HashMap<>();42        this.top = m * n;43    }44}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int total;8private9  Random rand = new Random();10private11  Map<Integer, Integer> mp = new HashMap<>();12public13  Solution(int m, int n) {14    this.m = m;15    this.n = n;16    this.total = m * n;17  }18public19  int[] flip() {20    int x = rand.nextInt(total--);21    int idx = mp.getOrDefault(x, x);22    mp.put(x, mp.getOrDefault(total, total));23    return new int[]{idx / n, idx % n};24  }25public26  void reset() {27    total = m * n;28    mp.clear();29  }30} /** * Your Solution object will be instantiated and called as such: * Solution31     obj = new Solution(m, n); * int[] param_1 = obj.flip(); * obj.reset(); */

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem