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.
This approach maps the 2D matrix to a 1D space, where each 0 cell is equally likely to be chosen and flipped to 1. It utilizes a hashmap to record changes, associating flipped 1D indices to the cells at the end of the list of available indices, which effectively "shrinks" the pool of zeros.
Implementation Explanation:
flip function generates a random index within the range of available slots. It retrieves the corresponding mapped index, decreasing the available slot count to ensure no repeats.reset method clears the map and resets the availability to full.Time Complexity: O(1) per flip operation as getting and setting in the hashmap is O(1).
Space Complexity: O(K) where K is the number of flipped cells recorded in the hashmap.
The Fisher-Yates shuffle is an algorithm used to generate a random permutation of a finite sequence, ideal for selecting random indices in the given problem. Each matrix cell is represented as a 1D element, and instead of mapping indices to a hashmap, we can shuffle the sequence using Fisher-Yates in a constrained manner to ensure uniform randomness.
Implementation Explanation:
C++
JavaScript
Time Complexity: O(1) per operation as index tracking uses constant time access.
Space Complexity: O(K) where K is the maximal space occupied by the unordered_map during flip operations.
| Approach | Complexity |
|---|---|
| Using a Hash Map to Track Flipped Cells | Time Complexity: O(1) per flip operation as getting and setting in the hashmap is O(1). |
| Using Fisher-Yates Shuffle | Time Complexity: O(1) per operation as index tracking uses constant time access. |
| Default Approach | — |
| 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 |
Random Flip Matrix | LeetCode 519 | Java • The TryIt Project • 1,082 views views
Watch 9 more video solutions →Practice Random Flip Matrix with our built-in code editor and test cases.
Practice on FleetCode