73. Set Matrix Zeroes

Problems

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

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:
Did you use extra space?
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?

Solution

• use first row and column to store the states
• use two variables to store the origin states of the headers
• when scanning the matrix, skip the headers

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    if (!matrix || matrix.length <= 0) {
        return
    }

    let height = matrix.length
    let width = matrix[0].length

    let isRowHeaderHasZero = false
    let isColHeaderHasZero = false

    // deal with the headers
    for (let row = 0; row < height; row += 1) {
        if (matrix[row][0] === 0) {
            isRowHeaderHasZero = true
            break
        }
    }

    for (let col = 0; col < width; col += 1) {
        if (matrix[0][col] === 0) {
            isColHeaderHasZero = true
            break
        }
    }

    // scan the matrix, skip the headers
    for (let row = 1; row < height; row += 1) {
        for (let col = 1; col < width; col += 1) {
             if (matrix[row][col] === 0) {
                matrix[row][0] = 0
                matrix[0][col] = 0
            }
        }
    }

    // set zero to the matrix
    for (let row = 1; row < height; row += 1) {
        if (matrix[row][0] === 0) {
            for (let i = 1; i < width; i += 1) {
                matrix[row][i] = 0
            }
        } else {
            for (let col = 1; col < width; col += 1) {
                if (matrix[0][col] === 0) {
                    matrix[row][col] = 0
                }
            }
        }
    }

    // set zero to the headers
    if (isRowHeaderHasZero) {
        for (let row = 0; row < height; row += 1) {
            matrix[row][0] = 0
        }
    }

    if (isColHeaderHasZero) {
        for (let col = 0; col < width; col += 1) {
            matrix[0][col] = 0
        }
    }
};