Watch 10 video solutions for Random Flip Matrix, a medium level problem involving Hash Table, Math, Reservoir Sampling. This walkthrough by The TryIt Project has 1,082 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104flip.1000 calls will be made to flip and reset.Problem Overview: You have an m x n matrix initially filled with 0s. Each call to flip() must randomly select a cell containing 0, change it to 1, and return its coordinates. A cell cannot be flipped twice. reset() restores the matrix to all zeros.
Approach 1: Hash Map to Track Flipped Cells (O(1) average time, O(k) space)
This approach treats the matrix as a flattened array of size m * n. Instead of storing the entire matrix, maintain a shrinking range of available indices. When flip() is called, generate a random index within the remaining range. A hash table maps used indices to the last available index, simulating a virtual swap similar to the end of an array. After selecting an index, decrease the available range so the same position cannot be chosen again. Each flip runs in O(1) average time with O(k) space where k is the number of flips. This technique relies on randomized algorithms to ensure uniform selection.
The key insight is avoiding storage of the full matrix. Instead of marking cells, you remap indices dynamically. If a random index was previously swapped, the hash map tells you its current mapped value. This keeps the selection uniform while minimizing memory usage.
Approach 2: Fisher-Yates Shuffle (O(1) per flip after O(mn) setup, O(mn) space)
Another option is to explicitly store all m * n cell indices in a list and apply the Fisher–Yates shuffle idea. Initially fill an array with numbers 0..(m*n-1). Each flip() selects a random index within the remaining range and swaps it with the last unused element. The returned value converts back to matrix coordinates using division and modulo.
This is the classic Fisher-Yates shuffle, commonly used for uniform random permutations. Each flip runs in O(1) time because it performs one random selection and one swap. However, it requires storing the entire array, leading to O(mn) space. For large matrices this can become expensive compared to the hash-map method.
Recommended for interviews: The hash map mapping technique is usually expected. It demonstrates understanding of space optimization and randomized index mapping. The Fisher–Yates approach is conceptually simpler and still correct, but interviewers often prefer the hash-map version because it avoids allocating O(mn) memory while keeping flip() constant time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Index Mapping | O(1) average per flip | O(k) | Best general solution when the matrix is large and you want to avoid storing all cells |
| Fisher-Yates Shuffle | O(1) per flip after O(mn) setup | O(mn) | Simpler implementation when memory is not a constraint |