Set matrix zeroes

Given a matrix if there is any value which is zero then set all the values in that column and row as zeroes.

Example

Input:
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

Output:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

We are going to see two different solutions for this problem.

Using HashSet to set matrix zeroes.

• We are going to use two different sets to for the columns and the rows which contain zeroes in the matrix.
• Then iterate the matrix and check if the current element is zero or not, if it is then store its row and column value in the set.
• Then get all the rows and columns from the set and update all the values of them to zero in matrix.

const setZeroes = (matrix) => {
    const zeroRow = new Set();
    const zeroCol = new Set();
    
    //Iterate matrix
    for(let i = 0; i < matrix.length; i++) {
        
        for(let j = 0; j < matrix[0].length; j++) {
            //if zero found then store its row and column
            if(matrix[i][j] === 0) {
                zeroRow.add(i);
                zeroCol.add(j);
            }
        }
    }
    
    //Update all the values of rows to 0
    for(let r of zeroRow) {
        for(let j = 0; j < matrix[0].length; j++) {
            matrix[r][j] = 0;
        }
    }
    
    //Update all the values of columns to 0
    for(let c of zeroCol) {
        for(let i = 0; i < matrix.length; i++) {
            matrix[i][c] = 0;
        }
    }
};

Input:
const arr = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
];
setZeroes(arr)
console.log(arr);

Output:
[[1,0,1],[0,0,0],[1,0,1]]

Time complexity: O(m * n);
Space complexity: O(m + n);

---

Efficient method

Our first approach works fine but it requires extra space to work. We can optimize it further to make it work without extra space.

• Iterate the matrix and check if there is any value zero then set its previous row and column value to 0.
• Then again iterate the matrix from bottom and check if the previous row or column value is 0 then set the current value to zero.
• This way we make sure we only update the existing zeroes column and row and not for the updated values.

const setZeroes = function(matrix) {
    let col0 = 1, row = matrix.length, col = matrix[0].length;
    
    for(let i = 0; i < row; i++) {
        if(matrix[i][0] === 0) col0 = 0;
        for(let j = 1; j < col; j++) {
            if(matrix[i][j] === 0) {
                matrix[i][0] =  matrix[0][j] = 0;
            }
        }
    }
    
    for(let i = row-1; i >= 0; i--) {
        for(let j = col-1; j > 0; j--) {
            if(matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
        }
        if(col0 === 0) matrix[i][0] = 0;
    }
};

Input:
const arr = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
];
setZeroes(arr)
console.log(arr);

Output:
[[1,0,1],[0,0,0],[1,0,1]]

Time complexity: O(m * n).
Space complexity: O(1).