##[leetcode] 73. Matrix Zero

Given a Matrix of m*n if an element is 0, then set all the elements of its row and column to 0, use the in-place algorithm

Advanced

• An intuitive approach is to use the extra space of O(mn), but this is not a good solution

• A simple improvement is to use the extra space of O(m+n), but this is still not the best solution.

• Solution using only one constant space

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

Solution I uses two tag arrays

We can use two tag arrays to record whether zero appears in each row and column.

Specifically, we first iterate through the array once, and if an element is zero, set the position of the corresponding tag array for the rows and columns in which it resides to true. Finally, we iterate through the array again and update the original array with the tag array.

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];
    int row[m], col[n];
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!matrix[i][j]) {
                row[i] = col[j] = true;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }

• Time Complexity: O(mn)
• Spatial Complexity: O(m+n)

Solution II uses two marker variables

The first row and column of the matrix can be used instead of the two tag arrays in method one to achieve the extra space of O(1). However, this will cause the first row and column of the original array to be modified to record whether they originally contained 0. Therefore, we need to use two additional marker variables to record whether the first row and column originally contained 0.

In the actual code, we first preprocess two marker variables, then use other rows and columns to process the first row and the first column, then use the first row and the first column to update the other rows and columns in turn, and finally use two marker variables to update the first row and the first column.

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];
    int flag_col0 = false, flag_row0 = false;
    for (int i = 0; i < m; i++) {
        if (!matrix[i][0]) {
            flag_col0 = true;
        }
    }
    for (int j = 0; j < n; j++) {
        if (!matrix[0][j]) {
            flag_row0 = true;
        }
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (!matrix[i][j]) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (!matrix[i][0] || !matrix[0][j]) {
                matrix[i][j] = 0;
            }
        }
    }
    if (flag_col0) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
    if (flag_row0) {
        for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }

• Time Complexity: O(mn)
• Spatial Complexity: O(1)

Solution III uses a marker variable

We can further refine Method 2 by using only one marker variable to record whether the first column was originally 0. This way, the first element of the first column marks whether the first row appears 0. However, to prevent the first element of each column from being updated in advance, we need to process the matrix elements in reverse order starting with the last row.

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];
    int flag_col0 = false;
    for (int i = 0; i < m; i++) {
        if (!matrix[i][0]) {
            flag_col0 = true;
        }
        for (int j = 1; j < n; j++) {
            if (!matrix[i][j]) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 1; j < n; j++) {
            if (!matrix[i][0] || !matrix[0][j]) {
                matrix[i][j] = 0;
            }
        }
        if (flag_col0) {
            matrix[i][0] = 0;
        }
    }
}

• Time Complexity: O(mn)
• Spatial Complexity: O(1)