519. Random Flip Matrix

MediumReservoir SamplingHash TableMathRandomized
Leetcode Link

Problem Description

In this LeetCode problem, we have a binary grid, matrix, which is initialized with all zeroes. The dimensions of the matrix are m x n. Our task is to design an algorithm that can randomly select an index (i, j) for which matrix[i][j] == 0, then flip that value to 1. It's crucial that each zero in the matrix is equally likely to be flipped. This means the selection process must be uniformly random. Once a zero is flipped to one, it can no longer be selected.

The problem requires us to solve this with a focus on efficiency: we should aim to use the random function as few times as possible and optimize both the time complexity (how fast the algorithm runs) and space complexity (how much memory it uses).

We also need to implement a Solution class:

  • Solution(int m, int n): This is the constructor that initializes the binary matrix with dimensions m x n.
  • int[] flip(): This function flips a random zero in the matrix to one and returns the index [i, j] of that element.
  • void reset(): This function sets all the values in the matrix back to zero.

Intuition

When trying to maintain the uniform random selection of zeros in the matrix while flipping and preventing a zero that's already been flipped to one from being flipped again, a direct approach of checking every time if an element is zero can lead to a large number of calls to the random function which is not efficient. To avoid this, we can use a mapping strategy.

The intuition behind the solution is to simulate the matrix in a linear fashion rather than as a 2D grid. We can imagine that each cell of the matrix is an element in an array (linearly indexed from 0 to m*n - 1). The goal is to randomly pick an element from this array. Once it's picked, we need to ensure it's not selected again.

An efficient way to do this is as follows:

  • Randomly pick an index in the linear representation of the matrix.
  • If it's the first time the index is picked and it's not in the mapping (which implies the cell is currently 0), we store the mapping of this index to the actual last index of the array.
  • If the index has been picked before, we use the mapping to find the new, swapped index which we know is 0.
  • Each time we "flip" a cell, we decrement the range of indices we are picking from by one. This is because there's now one less 0 to choose from.
  • By storing a mapping that swaps the picked index with the last index in the range, we can continue to pick random indexes while knowing they will always correspond to a 0 without having to verify each cell in the 2D grid. This is a space-efficient way to keep track of flipped indices.

This approach minimizes the number of calls to the random function, since each call results in a unique flip, and there's no need to repeat random calls to find the next zero to flip. The use of mappings ensures efficient utilization of space and fast access times.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The solution approach utilizes a hash map (or a dictionary in Python) to implement the mapping between the indices of the matrix and the indices of a linear array that represents our matrix. This hash map is used to keep track of which indices have already been flipped. Additionally, a variable to keep track of the total number of zeroes left unflipped in the matrix is used, which also reduces with each flip.

Let's walk through the algorithm step by step:

  1. Initialization (__init__ Method):

    • Store the dimensions of the matrix (m and n) in self.m and self.n.
    • Calculate the total number of elements in the matrix (m * n) and store it in self.total.
    • Initialize an empty dictionary self.mp to hold the mappings.
  2. The Flip Function (flip Method):

    • Decrement the self.total count since we are about to flip a zero to one, effectively reducing the count of zeroes by one.
    • Generate a random index x from 0 to self.total - 1. The number self.total acts as the range for the random numbers that corresponds to the number of zeroes left in the matrix.
    • Check if x is already in the mapping (self.mp). If it's not, use x; if it is, get the mapped value from self.mp. This value idx is the linear index of the zero value we will flip.
    • Update the mapping: set self.mp[x] to be whatever is currently mapped to self.total, which is essentially the index of the last '0'. If self.total is not in the map, it simply maps to itself (since that is the current 'last index' that hasn't been flipped yet).
    • Convert idx from a linear index to a 2D index (which corresponds to matrix indices (i, j)), and return it.

    The crucial point is that the map holds a swap record of positions. If we've previously replaced the value at a position, then the map entry points to the last unflipped index, otherwise it points to itself.

  3. The Reset Function (reset Method):

    • Reset self.total back to m * n, as we are resetting all values of the matrix back to zero.
    • Clear the dictionary self.mp, because no indices will be flipped anymore.

By following this approach, we avoid redundant random function calls and iterations over the matrix to check if an element is zero. The time complexity of the flip method is O(1) on average since it requires a constant number of hash map and assignment operations. The space complexity is also optimized because instead of storing the entire matrix, we only store the indices that have been flipped; so at most the space will be O(min(m*n, number of flips)). The reset method also operates in O(1) time since it simply resets the two variables without the need to go through the matrix.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's consider a small matrix of size 2x3, which means our matrix has 2 rows and 3 columns, or a 2 x 3 grid. Initially, all elements are 0, looking like this:

10 0 0
20 0 0

We can map this grid to a linear array from indices 0 to 5, with each cell's linear index calculated by i * n + j where (i, j) are the row and column numbers of the matrix and n is the number of columns.

Now, let's walk through the solution algorithm with this matrix:

  1. Initialization:

    • The matrix size is 2x3, so we initialize self.m = 2, self.n = 3, and thus self.total = self.m * self.n = 6.
    • We also initialize an empty dictionary self.mp = {}, which will hold our mappings.
  2. First Flip:

    • We currently have self.total = 6, meaning there are 6 zeros available to flip.
    • Let's say we pick a random index x = 2.
    • Since 2 is not in self.mp, we use it directly. No mapping is needed yet.
    • We decrement self.total to 5.
    • We determine the 2D matrix position of this index 2. We have i = idx // self.n = 2 // 3 = 0, and j = idx % self.n = 2 % 3 = 2. So, matrix[0][2] is flipped from 0 to 1.
    • The matrix is now:
10 0 1
20 0 0
  1. Second Flip:
    • self.total is now 5.
    • Suppose the random function gives us x = 4.
    • Index 4 is not in self.mp, so we flip the cell at linear index 4 to 1, decrement self.total to 4, and update self.mp[4] = 5 to map to the last index of the current zero range.
    • In the 2D matrix, i = 4 // 3 = 1 and j = 4 % 3 = 1. So, matrix[1][1] changes to 1.
    • The matrix now looks like:
10 0 1
20 1 0
  1. Third Flip:
    • Now self.total is 4.
    • We pick a random index x = 2. This time x is in self.mp. However, because we haven't remapped index 2 yet (since it was directly used the first time), we use it as is again, decrement self.total to 3.
    • We get matrix indices i = 2 // 3 = 0 and j = 2 % 3 = 2. But since matrix[0][2] is already flipped to 1, we attempt to update self.mp by making self.mp[2] point to self.mp[4], which is 5. This effectively swaps the picked index with one that hasn't been used.
    • Since index 5 has not been flipped, we then use index 5 to flip in the matrix, which gives us i = 5 // 3 = 1 and j = 5 % 3 = 2. matrix[1][2] is flipped.
    • The updated matrix is:
10 0 1
20 1 1
  1. Reset:
    • If we want to reset the matrix, we set self.total back to 6 and clear self.mp.
    • Our matrix is back to its initial state:
10 0 0
20 0 0

In summary, the linear mapping approach allows us to flip each zero in the matrix with an equal probability, while minimizing calls to the random function and avoiding checking all matrix cells multiple times. The use of a mapping dictionary efficiently tracks the cells that have been flipped, and the total variable ensures that the indices correspond to zeroes in our grid.

Not Sure What to Study? Take the 2-min Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Python Solution

1from random import randint
2from typing import List
3
4
5class Solution:
6    def __init__(self, m: int, n: int):
7        # Initialize the number of rows(m) and columns(n)
8        self.num_rows = m
9        self.num_cols = n
10        # Calculate and store the total number of cells
11        self.total_cells = m * n
12        # Initialize a dictionary to keep track of flipped cell indices
13        self.flip_map = {}
14
15    def flip(self) -> List[int]:
16        # Decrease the count of available cells
17        self.total_cells -= 1
18        # Generate a random index to flip
19        x = randint(0, self.total_cells)
20        # Get the actual index to flip using the flip_map to handle collisions
21        idx = self.flip_map.get(x, x)
22        # Map the current index to a new random index
23        self.flip_map[x] = self.flip_map.get(self.total_cells, self.total_cells)
24        # Convert the 1D index to 2D coordinates (row and column)
25        return [idx // self.num_cols, idx % self.num_cols]
26
27    def reset(self) -> None:
28        # Reset the total number of available cells
29        self.total_cells = self.num_rows * self.num_cols
30        # Clear the flip_map dictionary
31        self.flip_map.clear()
32
33
34# Your Solution object will be instantiated and called as such:
35# obj = Solution(m, n)
36# param_1 = obj.flip()
37# obj.reset()
38

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3import java.util.Random;
4
5class Solution {
6    private int rows;
7    private int cols;
8    private int totalCells;
9    private Random randomGenerator = new Random();
10    private Map<Integer, Integer> flippedCellsMap = new HashMap<>();
11
12    // Constructor with parameters for number of rows and columns
13    public Solution(int m, int n) {
14        this.rows = m;
15        this.cols = n;
16        this.totalCells = m * n;
17    }
18
19    // Flip a random cell and make sure not to flip the same cell again
20    public int[] flip() {
21        // Get a random index from the remaining cells
22        int randomIndex = randomGenerator.nextInt(totalCells--);
23
24        // Find the actual cell index to be flipped, taking into account any previously flipped cells
25        int cellIndex = flippedCellsMap.getOrDefault(randomIndex, randomIndex);
26
27        // Mark this cell as flipped by mapping it to the last available cell's index, effectively removing it from the pool of possible flips
28        flippedCellsMap.put(randomIndex, flippedCellsMap.getOrDefault(totalCells, totalCells));
29
30        // return the 'flipped' cell's row and column as an array
31        return new int[] {cellIndex / cols, cellIndex % cols};
32    }
33
34    // Reset the state of the Solution to allow all cells to be flipped again
35    public void reset() {
36        totalCells = rows * cols;
37        flippedCellsMap.clear();
38    }
39}
40
41/**
42 * The following are the typical operations that will be performed on an instance of the Solution class:
43 * 
44 * Solution obj = new Solution(m, n);
45 * int[] param_1 = obj.flip();
46 * obj.reset();
47 */
48

C++ Solution

1#include <unordered_map>
2#include <random>
3#include <vector>
4
5class Solution {
6private:
7    int rows;                                 // Number of rows in the matrix
8    int cols;                                 // Number of columns in the matrix
9    int totalCells;                           // Total number of cells in the matrix
10    std::random_device rd;                    // Random device to seed the generator
11    std::mt19937 randomGenerator{rd()};       // Mersenne Twister random number generator
12    std::unordered_map<int, int> flippedCellsMap; // Maps flipped cell index to a new index
13  
14public:
15    // Constructor with parameters for number of rows and columns of the matrix
16    Solution(int m, int n) : rows(m), cols(n), totalCells(m * n) {}
17
18    // Flip a random cell and ensure not to flip the same cell again
19    std::vector<int> flip() {
20        // Get a random index from the remaining unflipped cells
21        std::uniform_int_distribution<> distrib(0, totalCells - 1);
22        int randomIndex = distrib(randomGenerator);
23        totalCells--; // Decrement the count of total cells as one will be flipped
24
25        // Find the actual cell index to be flipped, taking into account any previously flipped cells
26        int cellIndex = flippedCellsMap.count(randomIndex) ? flippedCellsMap[randomIndex] : randomIndex;
27
28        // Mark this cell as flipped by mapping the chosen random index to the last available cell's index,
29        // effectively removing it from the pool of possible flips.
30        flippedCellsMap[randomIndex] = flippedCellsMap.count(totalCells) ? flippedCellsMap[totalCells] : totalCells;
31
32        // Calculate and return the 'flipped' cell's coordinates as a vector containing row and column
33        return {cellIndex / cols, cellIndex % cols};
34    }
35
36    // Reset the state of the Solution to allow all cells to be flipped again
37    void reset() {
38        totalCells = rows * cols;
39        flippedCellsMap.clear();
40    }
41};
42
43/**
44 * The following are the typical operations that will be performed on an instance of the Solution class:
45 * 
46 * Solution obj(m, n);
47 * std::vector<int> params = obj.flip();
48 * obj.reset();
49 */
50

Typescript Solution

1// Typescript doesn't support public/private keywords without a class, so leaving it out
2
3// Define variables for rows, columns, and total cells
4let rows: number;
5let cols: number;
6let totalCells: number;
7
8// Instantiate a Random number generator
9const randomGenerator: () => number = () => Math.floor(Math.random() * totalCells);
10
11// Define a map to keep track of flipped cells
12const flippedCellsMap: Map<number, number> = new Map<number, number>();
13
14// Initialize the global state with number of rows and columns
15function initializeSolution(m: number, n: number): void {
16  rows = m;
17  cols = n;
18  totalCells = m * n;
19}
20
21// Flip a random cell and make sure not to flip the same cell again
22function flip(): number[] {
23  // Get a random index from the remaining cells
24  const randomIndex: number = randomGenerator();
25  totalCells -= 1;
26
27  // Find the actual cell index to be flipped, taking into account any previously flipped cells
28  const cellIndex: number = flippedCellsMap.get(randomIndex) ?? randomIndex;
29
30  // Mark this cell as flipped by mapping it to the last available cell's index, effectively removing it from the pool of possible flips
31  flippedCellsMap.set(randomIndex, flippedCellsMap.get(totalCells) ?? totalCells);
32
33  // Return the 'flipped' cell's row and column as an array
34  return [Math.floor(cellIndex / cols), cellIndex % cols];
35}
36
37// Reset the state to allow all cells to be flipped again
38function reset(): void {
39  totalCells = rows * cols;
40  flippedCellsMap.clear();
41}
42
43// Example of usage:
44// initializeSolution(m, n);
45// const param_1 = flip();
46// reset();
47
Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

Time Complexity

flip():

  • For selecting a random index and flipping, the operations performed are constant time operations, including getting and setting values in a dictionary. Therefore, the time complexity of flip() is O(1).

reset():

  • Clearing the hash map is an O(1) operation assuming average case scenario where hash table operations have constant time complexity. However, if we consider the worse case scenario, where we have to traverse the hash map to clear it, it would have a time complexity of O(k) where k is the number of elements in the hash map. Since k can be at most the total number of flips which is m * n, the worst case time complexity is O(m * n).

Space Complexity

  • The hash map self.mp is used to keep track of the flipped indices, which can have at most m * n entries if all possible flips have occurred. Therefore, the maximum space complexity is O(m * n) for storing these mappings.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫