Leetcode 73 Set Matrix Zeroes

Set Matrix Zeroes – LeetCode

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s. You must do it in place

There are straight forward solutions for this problem but they are require extra space. The best solution only ask for O(1) of space.

The reason why we need extra space in the first place is because we need to store the information about which row and column should be filled with 0’s. Instead of storing the info in another matrix or another set, why do we use the first column and the first row to store them? But we would also need to keep a record of whether the first row and first column should be filled with 0’s since the original information will be overwritten. Below is the solution with detailed comments

Javascript:

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    const y = matrix.length
    const x = matrix[0].length
    
    // Since we will be using the first row and first column to store info about whether each row
    // should be filled, the original info will be lost
    // So we use this to keep the information about whether we should 
    // fill the first row and first column
    let shouldFillFirstRow = false;
    let shouldFillFirstColumn = false;

    // set shouldFillFirstRow
    for(let i = 0; i < x; i++) {
        if(!matrix[0][i]) {
            shouldFillFirstRow = true;
            break;
        }
    }
    
    // set shouldFillFirstColumn
    for(let i = 0; i < y; i++) {
        if(!matrix[i][0]) {
            shouldFillFirstColumn = true;
            break;
        }
    }

    // now we will loop through the matrix except for the first row and first column and
    // store the info where the whole role and whole column should be filled, by setting
    // the first cell in the column or row to 0
    for(let i = 1; i < y; i++) {
        for(let j = 1; j < x; j++) {
            if(!matrix[i][j]) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // fill cells with 0's if needed, except for the first row and first column
    for(let i = 1; i < y; i++) {
        for(let j = 1; j < x; j++) {
            if(!matrix[i][0] || !matrix[0][j]) {
                matrix[i][j] = 0;
            }
        }
    }

    // fill the first row if needed
    if(shouldFillFirstRow) {
        for(let i = 0; i < x; i++) {
            matrix[0][i] = 0;
        }
    }

    // fill the first row if needed
    if(shouldFillFirstColumn) {
        for(let i = 0; i < y; i++) {
            matrix[i][0] = 0;
        }
    }

};

Time Complexity:
O(nm)

Space Complexity:
O(1)

Leetcode 73 Set Matrix Zeroes

Leetcode 73 Set Matrix Zeroes

Leave a Reply Cancel reply