Leetcode in JS: Matrix Zeros

Question:
https://leetcode.com/problems/set-matrix-zeroes/

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:

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:

0 | 1 | 2
2 | 2 | 3
1 | 1 | 0

it should be:

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:

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.

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

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 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.

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

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:

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.

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.

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.

// 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:

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:

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

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:

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

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