Set Matrix Zeroes medium

Problem Statement

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

Example 1

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Steps

The naive approach would be to iterate through the matrix, and whenever we find a 0, iterate through the corresponding row and column to set all elements to 0. However, this is inefficient, leading to O(mn^2) or O(m^2n) time complexity. A more efficient approach utilizes the first row and first column to store information about whether a row or column needs to be zeroed.

1. First Row and Column Check: Iterate through the matrix. If you find a 0, mark the first element of its row (matrix[i][0]) and the first element of its column (matrix[0][j]) as 0. We use the first row and column as marker arrays. Handle the case where the first row or column itself contains a zero carefully.

2. Zeroing Rows and Columns: Iterate through the matrix except the first row and column. If matrix[i][0] or matrix[0][j] is 0, set matrix[i][j] to 0.

3. Zeroing First Row and Column (if necessary): Finally, if matrix[0][0] is 0, zero out the entire first row. If any other element in the first column is 0, zero out the entire first column.

Explanation

The key optimization is using the first row and column as auxiliary space to store information about which rows and columns should be zeroed. This avoids redundant traversals and improves efficiency. We avoid extra space except for a few constant variables.

Code

function setZeroes(matrix: number[][]): void {
    const m = matrix.length;
    const n = matrix[0].length;
    let firstRowZero = false;
    let firstColZero = false;

    // Check first row and column for zeros and mark
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            firstColZero = true;
        }
    }
    for (let j = 0; j < n; j++) {
        if (matrix[0][j] === 0) {
            firstRowZero = true;
        }
    }

    // Mark rows and columns with zeros using first row and column
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Zero out rows and columns based on marks
    for (let i = 1; i < m; i++) {
        if (matrix[i][0] === 0) {
            for (let j = 0; j < n; j++) {
                matrix[i][j] = 0;
            }
        }
    }
    for (let j = 1; j < n; j++) {
        if (matrix[0][j] === 0) {
            for (let i = 0; i < m; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    //Zero out first row and column if necessary
    if (firstRowZero) {
        for (let j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
    if (firstColZero) {
        for (let i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
};

Complexity

• Time Complexity: O(m*n), as we iterate through the matrix twice.
• Space Complexity: O(1), as we use only a constant amount of extra space. The first row and column of the input matrix are used for marking.