Question: https://leetcode.com/problems/set-matrix-zeroes/ ![](https://i.imgur.com/dgvagVa.png) *Screenshot from Leetcode* ## Main concepts in this question - Space complexity - in-place ### Space complexity In short, it means how much memory space you have used in your code. We usually use Big-O notation to represent space complexity. Below is Big-O notation of space complexity, starting from the best to the worst: ```javascript O(1) // constant space O(log n) // log of input size O(n) // input size O(nlog n) // n times of the log of input size O(n^2) // square of the input size ``` If you are not familiar with log or the meaning of log n, this may be a good article for you: https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf ### In-place The idea of in-place is very straightforward. In this question, it means that we should directly change the value in the input matrix, instead of creating a new array and returning it. ## Solutions Back to the question, these are the hints provided in Leetcode: - A straight forward solution using O(mn) space is probably a bad idea. - A simple improvement uses O(m + n) space, but still not the best solution. - Could you devise a constant space solution? ## Common mistake to avoid Whenever we update the values to 0, the update should only happen once. Otherwise all values in the matrix will be 0. Based on the questions, when we have 0, we set the entire row and column to 0. For example, if we have an original matrix like this: ```javascript 0 | 1 | 2 2 | 2 | 3 1 | 1 | 0 ``` it should be: ```javascript 0 | 0 | 0 0 | 2 | 0 0 | 1 | 0 ``` Even though now the 2nd and 3rd row contains 0, we should not continue updating the whole 2nd, 3rd row and the 2nd column to be 0. Otherwise all the values will be 0: ```javascript 0 | 0 | 0 0 | 0 | 0 0 | 0 | 0 ``` ## O(mn) solution O(mn)space solution is not recommended since it will not be done in-place. Here are my steps of O(mn) solution: 1. Create a temporary matrix by copying the original matrix 2. Create an temporary array, `colZeroRecord`, which its length is `matrix[0].length`, for recording which column contains 0. 3. We will deal with all the **rows** first. Scan through the **original matrix**, if there is 0 : - Set the whole corresponding array in the **temporary matrix** to 0. - Set the corresponding value in the temporary array, `colZeroRecord` to 0 For example, we meet an array like this: `[1,0,2]`: - We will change it to `[0,0,0]`. - The `colZeroRecord` will be changed to `[1,0,1]` from `[1,1,1]` (because I initialized it with all 1 at the beginning) Now we have checked all the rows, but we still haven't check the column. We have to scan through the **temporary matrix** and check if the value should be 0 or not by looking into `colZeroRecord`. Finally, copy the whole temporary matrix to the original matrix and return it. ```javascript var setZeroes = function(matrix){ // Copy the original array const tempMatrix = JSON.parse(JSON.stringify(matrix)); // Temporary array for recording which column will be 0 const colZeroRecord = Array(matrix[0].length).fill(1); // Scan through the original matrix for(let row = 0; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ if(matrix[row][col] === 0){ // Set the whole corresponding array in colZeroRecord to 0 tempMatrix[row] = Array(matrix[0].length).fill(0); // Set the corresponding value in colZeroRecord to 0 colZeroRecord[col] = 0; } } } // Scan through the temporary matrix with checking the values in colZeroRecord for(let row = 0; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ if(colZeroRecord[col] === 0){ tempMatrix[row][col] = 0; } } } // Copy the whole temporary matrix to the input matrix for(let row = 0; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ matrix[row][col] = tempMatrix[row][col] } } return matrix; } ``` ### Result ![](https://i.imgur.com/YyrbdnZ.png) ### Summary The space complexity is O(mn) because we create a copy of the original matrix. - Let m = matrix.length (height of the matrix) - Let n = matrix[0].length (width of the matrix) Therefore, the size of the copied matrix is m*n. The memory we use is O(mn). ## O(m+n) solution For O(m+n) and O(1) solution, I mainly take reference from the concepts suggested in the [video](https://www.youtube.com/watch?v=T41rL0L3Pnw) here, then write them in JavaScript. 1. Create 2 arrays. One is to record which column has 0, another one is to record which row has 0. 2. Scan through the whole original matrix, if there's a row contains 0, record it in `colZero` and `rowZero`. **We don't change anything in the original matrix right now.** 3. Based on the record results we have in `colZero` and `rowZero`, now we update the original matrix. ```javascript var setZeroes = function(matrix) { const colZero = Array(matrix[0].length); const rowZero = Array(matrix.length); for(let row = 0; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ if(matrix[row][col] === 0){ colZero[row] = 0; rowZero[col] = 0; } } } for(let row = 0; row < matrix.length; row++){ if(colZero[row] === 0){ matrix[row] = Array(matrix[0].length).fill(0); continue; // because the whole array is already set to 0, // no need to check each value's column has 0 or not, // for updating the individual value to 0. } for(let col = 0; col < matrix[0].length; col++){ if(rowZero[col] === 0){ matrix[row][col] = 0; } } } return matrix; } ``` ### Result ![](https://i.imgur.com/avsZA4F.png) ### Summary The solution is O(m+n), because we create 2 arrays for recording which rows and columns will have 0: `colZero` = the width of the matrix (m) `rowZero` = the height of the matrix (n) Therefore the space complexity is m+n. In Big-O notation is O(m+n). ## O(1) solution We use 2 array to record which row and column have 0 in the previous solution. To improve the memory we used (i.e O(m+n)), we can use the **1st row and the 1st column** in the original matrix for doing the record, instead of creating 2 new arrays. In the following solution, we just have to create **1** variable. The complete solution: ```javascript var setZeroes = function(matrix) { const firstRowHasZero = matrix[0].includes(0); // Start from 2nd row for(let row = 1; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ if(matrix[row][col] === 0){ matrix[0][col] = 0; matrix[row][0] = 0; } } } // Look at 1st row in the matrix, update each row for(let row = 1; row < matrix.length; row++){ if(matrix[row][0] === 0){ matrix[row] = Array(matrix[0].length).fill(0); } } // Look at 1st column in the matrix, update each cell in the matrix for(let row = 1; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ if(matrix[0][col] === 0){ matrix[row][col] = 0; } } } if(firstRowHasZero) { matrix[0] = Array(matrix[0].length).fill(0); } return matrix; } ``` Let's look at it step by step: - Create a variable that records the first row of the input matrix has 0 or not. The value is a Boolean. The reason why it is necessary will be explained further later. ```javascript const firstRowHasZero = matrix[0].includes(0); ``` - Scan through the matrix, if there is 0, make a record in the 1st array in the matrix. Also, we need to make a record in the 1st value of the array that we are iterating. Note that: Since we will **use the 1st row in the matrix** to record which column will have 0, when we are scanning, we have to **start from the 2nd row**. ```javascript for(let row = 1; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ if(matrix[row][col] === 0){ matrix[0][col] = 0; matrix[row][0] = 0; } } } ``` - We have finished recording which row & column have 0. Now, we update the matrix based on the 1st row and 1st column of the matrix. ```javascript // Look at 1st row in the matrix, update each row for(let row = 1; row < matrix.length; row++){ if(matrix[row][0] === 0){ matrix[row] = Array(matrix[0].length).fill(0); } } // Look at 1st column in the matrix, update each cell in the matrix for(let row = 1; row < matrix.length; row++){ for(let col = 0; col < matrix[0].length; col++){ if(matrix[0][col] === 0){ matrix[row][col] = 0; } } } ``` - Based on the Boolean we have created, update the 1st row of the matrix: ```javascript if(firstRowHasZero) { matrix[0] = Array(matrix[0].length).fill(0); } ``` ### why do we need that 1 variable? That's because there will be an overlap of the 1st row and 1st column, like this: ![](https://i.imgur.com/dDP6Ad1.png) For example, if we have a matrix:` [ [1,1,1],[0,1,1],[1,1,1] ]` When we are scanning the 2nd row, we have a 0 for the 1st column of the 2nd row, so we have to make a record on **the 1st value of the 1st row and 1st value of that row** ![](https://i.imgur.com/qaajmWO.png) Notice that the 1st value of the 1st row is changed to be 0. That's problematic when we later update each row in the matrix based on the 1st value of that row. Like this: ![](https://i.imgur.com/BOmbYBO.png) The 1st row will be all 0, which is wrong because as mentioned before, **the update should only happen once**. The mistake happens since **the 1st value is 'polluted' already when we are scanning through all rows for making the records.** Hence, **it's necessary to create a variable to check whether the 1st row contains 0 or not initially.** When we update the 1st row, we will do the checking **based on this variable instead of the 1st value of the 1st row.** ### Result ![](https://i.imgur.com/cF2uonZ.png) ### Summary The solution is O(1). We only create 1 variable, `firstRowHasZero` in this solution. ## Reference: https://www.youtube.com/watch?v=BnCJaHiSodg&ab_channel=nETSETOS https://www.youtube.com/watch?v=T41rL0L3Pnw&ab_channel=NeetCode

alysachan830

Leetcode in JS: Matrix Zeros

Join Our Newsletter. No Spam, Only the good stuff.