Set Matrix Zeroes

JavaView on GFG

Time: O(n*m)

Space: O(1)

Intuition

Set entire row and column to 0 if element is 0. Mark rows/cols first, then zero them.

Algorithm

1Find all (r,c) with 0. Collect rows and cols to zero. Zero them in second pass.

Common Pitfalls

•Do not zero while scanning (would create false zeros). Mark first, zero second.

Set Matrix Zeroes.java

Java

// Approach: Use first row and column as markers. Scan for zeros, mark row/col, then zero out marked rows/cols.
// Time: O(n*m) Space: O(1)
class Solution {
    public void setMatrixZeroes(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;

        int col0 = 1;
        // step 1: Traverse the matrix and
        // mark 1st row & col accordingly:
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) {
                    // mark i-th row:
                    mat[i][0] = 0;

                    // mark j-th column:
                    if (j != 0)
                        mat[0][j] = 0;
                    else
                        col0 = 0;
                }
            }
        }

        // Step 2: Mark with 0 from (1,1) to (n-1, m-1):
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (mat[i][j] != 0) {
                    // check for col & row:
                    if (mat[i][0] == 0 || mat[0][j] == 0)
                        mat[i][j] = 0;
                }
            }
        }

        // step 3: Finally mark the 1st col & then 1st row:
        if (mat[0][0] == 0) {
            for (int j = 0; j < m; j++)
                mat[0][j] = 0;
        }
        if (col0 == 0) {
            for (int i = 0; i < n; i++)
                mat[i][0] = 0;
        }
    }
}

Was this solution helpful?