Set Matrix Zeroes (LC 73)

Pattern: In-place matrix marking (first row/column as flags)
Difficulty: Medium
Key Concept: If matrix[i][j] == 0, row i and column j must become zero; store which rows/cols need clearing using O(1) extra space by repurposing the first row and first column as bitmaps, plus two booleans for overlap.

Problem Statement

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

Input: int[][] matrix
Output: void (mutate matrix)

---

1. Algorithm & Pseudocode

Brute force

1. Copy the entire matrix to another m×n array.
2. In the copy, for each zero in the original, mark positions to zero.

Or: use boolean[m][n] “to zero” — still O(mn) space.

Optimal

firstRowHasZero = any zero in row 0
firstColHasZero = any zero in col 0

for r from 1 to m-1:
  for c from 1 to n-1:
    if matrix[r][c] == 0:
      matrix[r][0] = 0
      matrix[0][c] = 0

for r from 1 to m-1:
  if matrix[r][0] == 0:
    set entire row r to 0

for c from 1 to n-1:
  if matrix[0][c] == 0:
    set entire column c to 0

if firstRowHasZero: zero row 0
if firstColHasZero: zero col 0

---

2. Step-by-Step Analysis (Beginner-Friendly)

• You cannot zero immediately while scanning: you might read a 0 that was originally non-zero but was cleared early.
• Markers in row 0 and col 0 record “this row/col must die” without using extra arrays.
• Order matters: use rows/cols 1..end first for clearing, then handle row 0 and col 0 using the two booleans so you do not lose the marker bits before they are read.

---

3. The Dry Run

Initial:
      c0  c1  c2
r0     1   1   1
r1     1   0   1
r2     1   1   1

Step	firstRowZero?	firstColZero?	After marking (r≥1,c≥1) cell (1,1)=0
scan row0	false	—	—
scan col0	—	false	—
inner	—	—	set matrix[1][0]=0, matrix[0][1]=0

Matrix after markers (conceptually):

      1   0   1
      0   0   1
      1   1   1

Zero rows 1.. using col0; cols 1.. using row0; row0/col0 flags false → final:

      1   0   1
      0   0   0
      1   0   1

---

4. Java Solution

Brute Force

class SolutionBrute {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[][] kill = new boolean[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (matrix[r][c] == 0) {
                    for (int j = 0; j < n; j++) kill[r][j] = true;
                    for (int i = 0; i < m; i++) kill[i][c] = true;
                }
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (kill[r][c]) matrix[r][c] = 0;
            }
        }
    }
}

Time: O(mn(m+n)) worst if you mark row/col per zero naively inside nested loops — can be O(mn) with separate row/col boolean arrays.

Cleaner O(mn) space brute: boolean[] row, boolean[] col.

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

Time: O(mn), Space: O(m + n).

Optimal

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;

        for (int c = 0; c < n; c++) {
            if (matrix[0][c] == 0) row0 = true;
        }
        for (int r = 0; r < m; r++) {
            if (matrix[r][0] == 0) col0 = true;
        }

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }

        for (int r = 1; r < m; r++) {
            if (matrix[r][0] == 0) {
                for (int c = 1; c < n; c++) matrix[r][c] = 0;
            }
        }
        for (int c = 1; c < n; c++) {
            if (matrix[0][c] == 0) {
                for (int r = 1; r < m; r++) matrix[r][c] = 0;
            }
        }

        if (row0) {
            for (int c = 0; c < n; c++) matrix[0][c] = 0;
        }
        if (col0) {
            for (int r = 0; r < m; r++) matrix[r][0] = 0;
        }
    }
}

Time: O(mn), Space: O(1) extra.

---

5. The “Java vs. Others” Edge

• Two-pass separation avoids overwriting marker cells prematurely.
• For boolean[][] on small matrices, memory is fine; interview gold is first row/col trick.
• Single cell matrix — both flags may be true; logic still holds.

---

6. Complexity Summary

Approach	Time	Space	Notes
Extra row/col arrays	O(mn)	O(m + n)	Simple, clear
First row/col markers	O(mn)	O(1)	Careful ordering

---

ASCII: Markers in first row/col

* = will become zero (marker or final)

Before zeros at (i,j):     Use row0 and col0 as flags:

  . . . .                    M . M .
  . X . .        =>          Z * Z .
  . . . .                    . * . .

M = marker in first row/col, Z = zeroed later