138.Set Matrix Zeroes

MediumBlind 75Math & Geometry · 3/8

Problem

Given an m x n integer matrix, if an element is 0, set its entire row and entire column to 0. Do it in place.

Only zeros present in the original matrix trigger this — zeros you write while processing must not spread further.

Examples

Input:  matrix = [[1,1,1],
                  [1,0,1],
                  [1,1,1]]
Output:          [[1,0,1],
                  [0,0,0],
                  [1,0,1]]

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

Constraints

m == matrix.length, n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

💡 Key Insight

The work splits into two phases: record which rows and columns contain an original zero, then apply the zeroing. Recording needs m + n flags — and the matrix's own first row and first column can store those flags. The first row and first column then need their own separate flag (one extra boolean for column 0), and they must be zeroed last so the markers are not destroyed before they are read.

Copy the Matrix (Brute Force)

TimeO(m · n · (m + n))SpaceO(m · n)

Intuition

Zeros written during processing must not trigger more zeroing. The simplest way to guarantee that is to read from an untouched copy and write into the real matrix.

Algorithm

copy = deep copy of matrix.
For every (r, c) where copy[r][c] == 0: zero all of row r and column c in matrix.

Visualization

copy (read only)     matrix (written)
1 1 1                1 0 1
1 0 1       -->      0 0 0
1 1 1                1 0 1

only copy[1][1] == 0 triggers zeroing of row 1 and column 1

Code

java

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] copy = new int[m][];
        for (int r = 0; r < m; r++) copy[r] = matrix[r].clone();

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (copy[r][c] != 0) continue; // only original zeros count
                for (int k = 0; k < n; k++) matrix[r][k] = 0;
                for (int k = 0; k < m; k++) matrix[k][c] = 0;
            }
        }
    }
}

Complexity

Time: O(m · n · (m + n)) — each original zero clears a row and a column.
Space: O(m · n) — the copy.

Row and Column Flag Arrays

TimeO(m · n)SpaceO(m + n)

Intuition

We do not need the whole copy — only which rows and which columns contain a zero. Record that in two boolean arrays, then zero every cell whose row or column is flagged.

Algorithm

zeroRow[m], zeroCol[n].
Pass 1: for every zero at (r, c), set zeroRow[r] = zeroCol[c] = true.
Pass 2: for every (r, c), if zeroRow[r] || zeroCol[c], set it to 0.

Visualization

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

zeroRow = [T, F, F]
zeroCol = [T, F, F, T]

row 0 flagged       -> 0 0 0 0
col 0, col 3 flagged-> 0 4 5 0
                       0 3 1 0

Code

java

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] zeroRow = new boolean[m];
        boolean[] zeroCol = new boolean[n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (matrix[r][c] == 0) {
                    zeroRow[r] = true;
                    zeroCol[c] = true;
                }
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (zeroRow[r] || zeroCol[c]) matrix[r][c] = 0;
            }
        }
    }
}

Complexity

Time: O(m · n) — two passes.
Space: O(m + n) — the two flag arrays.

First Row / Column as MarkersOptimal

TimeO(m · n)SpaceO(1)

Intuition

Reuse the matrix itself for the flags: matrix[r][0] = 0 means "row r must be zeroed", matrix[0][c] = 0 means "column c must be zeroed". Cell matrix[0][0] would have to serve both row 0 and column 0, so keep a separate boolean firstColZero for column 0 and let matrix[0][0] mean row 0.

Then fill the interior (r >= 1, c >= 1) from the markers, and finally handle row 0 and column 0 — last, because they hold the markers.

Algorithm

Pass 1: for every zero at (r, c):
- if c == 0, set firstColZero = true;
- otherwise set both markers matrix[r][0] = 0 and matrix[0][c] = 0.
Pass 2: for r in 1..m-1, c in 1..n-1: if matrix[r][0] == 0 || matrix[0][c] == 0, zero the cell.
If matrix[0][0] == 0, zero all of row 0.
If firstColZero, zero all of column 0.

Visualization

input            after pass 1 (markers)       after pass 2 (interior)      after rows/cols
0 1 2 0          0 1 2 0  firstColZero=T       0 1 2 0                      0 0 0 0
3 4 5 2   -->    3 4 5 2                -->    3 4 5 0             -->      0 4 5 0
1 3 1 5          1 3 1 5                       1 3 1 0                      0 3 1 0

(0,3) is a zero in row 0 -> marks matrix[0][3]=0 (already) and matrix[0][0]=0 (already)
(0,0) is in column 0      -> firstColZero = true

flowchart TD
    A["Pass 1: scan all cells<br/>record markers in row 0 / col 0"] --> B["Pass 2: interior r≥1, c≥1<br/>zero if row or col marker is 0"]
    B --> C{"matrix[0][0] == 0?"}
    C -->|"yes"| D["zero row 0"]
    C -->|"no"| E{"firstColZero?"}
    D --> E
    E -->|"yes"| F["zero column 0"]
    E -->|"no"| G["done"]
    F --> G

Code

java

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstColZero = false; // matrix[0][0] is reserved for row 0

        // Pass 1: record markers in row 0 and column 0
        for (int r = 0; r < m; r++) {
            if (matrix[r][0] == 0) firstColZero = true;
            for (int c = 1; c < n; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0; // row r must be zeroed
                    matrix[0][c] = 0; // column c must be zeroed
                }
            }
        }

        // Pass 2: interior cells, read markers but never overwrite them
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
            }
        }

        // Row 0 (its marker is matrix[0][0])
        if (matrix[0][0] == 0) {
            for (int c = 0; c < n; c++) matrix[0][c] = 0;
        }
        // Column 0 (its marker is the separate boolean)
        if (firstColZero) {
            for (int r = 0; r < m; r++) matrix[r][0] = 0;
        }
    }
}

Complexity

Time: O(m · n) — a constant number of passes.
Space: O(1) — one boolean; markers live inside the matrix.

Complexity Comparison

Approach	Time	Space
Copy Matrix	O(m · n · (m + n))	O(m · n)
Flag Arrays	O(m · n)	O(m + n)
In-place Markers	O(m · n)	O(1)

Common Pitfalls

Zeroing rows/columns immediately while scanning — new zeros then trigger more zeroing and the whole matrix collapses to zeros.
Letting matrix[0][0] stand for both row 0 and column 0 — you need one extra boolean.
Processing row 0 / column 0 before the interior — that wipes out the markers you still need.
Using a sentinel value like -1 or Integer.MIN_VALUE for "to be zeroed" — any int can appear in the input.