73. Set Matrix Zeroes - cocoder39/coco39_LC GitHub Wiki

73. Set Matrix Zeroes

Notes 2020:

use the first row and first column to record whether a row or column should be set to 0. We should not decide whether a row or column should be reset based on modified value. That said, once we modify first row or column, we can not use them to decide if first row/column should be reset. So we use 2 boolean values to record the status of first row and first column. Then use first row and first column to record all other positions.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        
        first_row = False
        for i in range(n):
            if matrix[0][i] == 0:
                first_row = True
                break
        
        first_col = False
        for i in range(m):
            if matrix[i][0] == 0:
                first_col = True  
                break
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        if first_row:
            for i in range(n):
                matrix[0][i] = 0
                
        if first_col:
            for i in range(m):
                matrix[i][0] = 0

========================================================================================================

if use an extra row and column to record which row and column need to be reset, it would take O(m + n) memory. here we use the row and column that would be reset, to record all other rows/columns that would be reset, it takes only O(1) memory. But careful programming is needed, otherwise would cause bugs.

tip:

  • use the row and column that would be reset to record
  • reset other rows/columns, then reset the row and column used to record
  • when reset other rows/columns, do not let the reset operation impact the row and column used to record.

O(m * n) time and O(1) memory

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int recordRow, recordCol;
        bool existZero = false;
        for (unsigned int i = 0; i < matrix.size(); i++) {
            for (unsigned int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == 0) {
                    if (! existZero) {
                        existZero = true;
                        recordRow = i;
                        recordCol = j;
                    } else {
                        matrix[i][recordCol] = 0;
                        matrix[recordRow][j] = 0;
                    }
                }
            }
        }
        if (! existZero)    return;
        
        for (unsigned int i = 0; i < matrix.size(); i++) {
            if (matrix[i][recordCol] == 0 && i != recordRow) //do not let set operation impact records
                helper(matrix, i, true);
        }
        for (unsigned int i = 0; i < matrix[recordRow].size(); i++) { //do not let set operation impact records
            if (matrix[recordRow][i] == 0 && i != recordCol)  
                helper(matrix, i, false);
        }
        helper(matrix, recordRow, true);
        helper(matrix, recordCol, false);
    }
private:
    void helper(vector<vector<int>>& matrix, int num, bool isRow) { //set a row/column to 0s
        if (isRow) {
            matrix[num] = vector<int>(matrix[num].size(), 0);
        } else {
            for (unsigned int i = 0; i < matrix.size(); i++) {
                matrix[i][num] = 0;
            }
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️