Set Matrix Zeroes

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.

Brute Force#

Scan the matrix and record the indices of all rows and columns that contain at least one zero. Then make a second pass, setting every cell in those rows and columns to zero. This is correct and runs in O(m*n) time but needs O(m + n) extra space for the row and column index lists — the optimal approach eliminates this overhead by reusing the matrix itself as storage.

• store rows and cols having zeroes
• Mark zeroes accordingly
• Not be in in-place

Time Complexity: O(m*n)

Space Complexity: O(m+n)

Optimal Approach#

Instead of a separate auxiliary array, repurpose the first row and first column of the matrix as marker arrays. First, record separately whether the first row and first column themselves originally contain a zero (two boolean flags). Then scan the interior of the matrix: whenever matrix[i][j] == 0, set matrix[0][j] = 0 and matrix[i][0] = 0 as markers. In a second pass, zero out any interior cell whose row-marker or column-marker is zero. Finally, use the two flags to conditionally zero out the first row and column. This achieves true O(1) extra space at the same O(m*n) time as the brute force.

• Use variables to store if first row or first col contains zero
• iterate through matrix and if zero found, mark first row ele and first col ele as zero
• Using first row and first col, mark whole row and col zeroes
• now using variables for firstRow and firstCol, mark zeroes in first row or col

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int isColOneZero = false, isRowOneZero = false;

        // identify if first row or first col has zeroes
        for(int row = 0; row < m; row++){
            if(matrix[row][0] == 0){
                isColOneZero = true;
                break;
            }
        }
        for(int col = 0; col < n; col++){
            if(matrix[0][col] == 0){
                isRowOneZero = true;
                break;
            }
        }

        // identify other zeroes
        for(int row = 0; row < m; row++){
            for(int col = 0; col < n; col++){
                if(matrix[row][col] == 0){
                    matrix[0][col] = 0;
                    matrix[row][0] = 0;
                }
            }
        }

        // mark matrix elements to zeroes based on markers in first row or col
        for(int row = 1; row < m; row++){
            for(int col = 1; col < n; col++){
                if(matrix[row][0] == 0 || matrix[0][col] == 0){
                    matrix[row][col] = 0;
                }
            }
        }

        //mark first row or col based on special markers
        if(isColOneZero){
            for(int row = 0; row < m; row++){
                matrix[row][0] = 0;
            }
        }
        if(isRowOneZero){
            for(int col = 0; col < n; col++){
                matrix[0][col] = 0;
            }
        }
    }
};

Time Complexity: O(m*n)

Space Complexity: O(1)