Chapter 1 - Problem 8 - Zero Matrix

Problem

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

Solution

If any cell of the matrix has a zero we can record its row and column number. All the cells of this recorded row and column can be marked zero in the next iteration.

Solution in C++ using two arrays

void nullifyColumnvector<int>>& matrix, int i {
    for(int j = 0, m = matrix.size(); j < m; ++j) {
        matrix[j][i] = 0;
    }
}

void nullifyRowvector<int>>& matrix, int i {
    for(int j = 0, n = matrix.at(0).size(); j < n; ++j) {
        matrix[i][j] = 0;
    }
}

void zeroMatrix_v1vector<int>>& matrix {
    std::unordered_set<int> columns;
    std::unordered_set<int> rows;

    for(int i = 0, m = matrix.size(); i < m; ++i) {
        for(int j = 0, n = matrix.at(0).size(); j < n; ++j) {
            if(matrix[i][j] == 0) {
                columns.insert(j);
                rows.insert(i);
            }
        }
    }

    for(int val : columns) {
        nullifyColumn(matrix, val);
    }

    for(int val : rows) {
        nullifyRow(matrix, val);
    }

}

• Time complexity: $O(M\cdot N)$
• Space complexity: $O(M+N)$

Solution in C++ using data structures

Example with explanation:

void zeroMatrix_v2vector<int>>& matrix {
    bool firstRow = false, firstColumn = false;
    // Step 1) Check if first row has a zero
    for(int i = 0, n = matrix.at(0).size(); i < n; ++i) {
        if(matrix[0][i] == 0) {
            firstRow = true;
            break;
        }
    }
    //Step 1) Check if first column has a zero
    for(int i = 0, m = matrix.size(); i < m; ++i) {
        if(matrix[i][0] == 0) {
            firstColumn = true;
            break;
        }
    }
    /* Step 2) Check zeros in the rest of the matrix and 
    set the first element of the correspondingrow and column to 0. */
    for(int i = 1, m = matrix.size(); i < m; ++i) {
        for (int j = 1, n = matrix.at(0).size(); j < n; ++j) {
            if(matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
        }
        
    }
    /* Step 3) For every cell, we check if the row or column 
    had been marked earlier by checking the respective first row cell or first column cell. 
    If any of them was marked, we set the value in the cell to 0. */
    for(int i = 1, m = matrix.size(); i < m; ++i) {
        for (int j = 1, n = matrix.at(0).size(); j < n; ++j) {
            if(matrix[0][j] == 0 || matrix[i][0] == 0)
                matrix[i][j] = 0;
        }
    }
    // Step 4) Nullify first row
    if(firstRow) {
        for(int i = 0, n = matrix.at(0).size(); i < n; ++i) {
            matrix[0][i] = 0;
        }
    }
    // Step 4) Nullify first column
    if(firstColumn) {
        for(int i = 0, m = matrix.size(); i < m; ++i) {
            matrix[i][0] = 0;
        }
    }
}

• Time complexity: $O(M\cdot N)$
• Space complexity: $O(1)$