Set Matrix Zeroes

Given an m × n integer matrix matrix, if an element is 0, set its entire row and column to 0s.

You must do it in place.

Examples

Prerequisites

Before attempting this problem, you should be comfortable with:

• 2D Array Indexing — accessing and modifying rows and columns by index
• Two-Pass Scanning — collecting information in one pass and applying it in a second
• In-Place Marker Technique — reusing existing matrix cells as metadata to avoid extra space
• Boolean Flag Variables — tracking edge cases like the first-row zero separately

1. Brute Force (Extra Copy)

Intuition

The naive approach is to record which cells are zero using a separate set, then iterate again and zero out the corresponding rows and columns. Alternatively, copy the matrix into a separate array and use that copy to decide which cells to zero in the original.

Algorithm

• Scan the matrix and collect all (r, c) positions where matrix[r][c] == 0 into a set.
• For each recorded (r, c), zero the entire row r and entire column c.

class Solution:
    def setZeroes(self, matrix):
        ROWS, COLS = len(matrix), len(matrix[0])
        zeroes = set()

        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    zeroes.add((r, c))

        for r, c in zeroes:
            for j in range(COLS):
                matrix[r][j] = 0
            for i in range(ROWS):
                matrix[i][c] = 0

class Solution {
    public void setZeroes(int[][] matrix) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        Set<int[]> zeroes = new HashSet<>();

        for (int r = 0; r < ROWS; r++)
            for (int c = 0; c < COLS; c++)
                if (matrix[r][c] == 0)
                    zeroes.add(new int[]{r, c});

        for (int[] pos : zeroes) {
            for (int j = 0; j < COLS; j++) matrix[pos[0]][j] = 0;
            for (int i = 0; i < ROWS; i++) matrix[i][pos[1]] = 0;
        }
    }
}

Time Complexity: O(m·n·(m+n)) — for each zero cell we scan its row and column.
Space Complexity: O(m·n) — the zeroes set can store up to m·n entries.

2. Row/Col Marker Arrays (O(m+n) Space)

Intuition

Instead of storing the exact coordinates of every zero, we just need to know which rows and which columns contain a zero. Two boolean arrays — rows[ROWS] and cols[COLS] — are enough. In the first pass, mark any row or column that contains a zero. In the second pass, set a cell to zero if its row or column was marked.

Algorithm

• Initialise rows = [False] * ROWS and cols = [False] * COLS.
• Pass 1: for every cell matrix[r][c] == 0, set rows[r] = True and cols[c] = True.
• Pass 2: for every cell, if rows[r] or cols[c] is True, set matrix[r][c] = 0.

Time Complexity: O(m·n) — two full scans of the matrix.
Space Complexity: O(m+n) — the two boolean arrays.

3. O(1) Space (First Row/Col as Markers)

Intuition

We can eliminate the extra rows[] and cols[] arrays by reusing the matrix itself. The first row acts as the column-marker array, and the first column acts as the row-marker array. The only cell that would be ambiguous is matrix[0][0]— it would need to represent both “first row has a zero” and “first column has a zero”. We resolve this by using a separate boolean rowZero to track whether the original first row contained a zero.

Algorithm

• Set rowZero = False.
• Pass 1: for each zero at [r][c], mark matrix[0][c] = 0. If r > 0, also mark matrix[r][0] = 0; otherwise set rowZero = True.
• Pass 2 (inner): for r in 1..ROWS-1, c in 1..COLS-1 — if matrix[0][c] == 0 or matrix[r][0] == 0, set matrix[r][c] = 0.
• If matrix[0][0] == 0, zero the entire first column.
• If rowZero, zero the entire first row.

Time Complexity: O(m·n) — two full scans plus a few single-pass sweeps.
Space Complexity: O(1) — only one extra boolean variable.

Common Pitfalls

Modifying the Matrix While Scanning

The most common mistake is zeroing rows and columns during the first scan. If you encounter a zero at [1][1] and immediately zero row 1 and column 1, then when you reach [2][1] it is now zero — and you incorrectly mark row 2 as well. Always separate the scan pass from the write pass.

Forgetting to Handle the First Row Separately

In the O(1) solution, matrix[0][0] serves as the first-column marker. If the first row also contains a zero, marking it via matrix[0][0] = 0 would be ambiguous — it would also trigger zeroing the entire first column even if column 0 had no zero. The fix is to track the first row with a separate rowZero flag and apply it last.

Incorrect Order of Final Updates in O(1) Solution

The first column and first row must be zeroed after the inner matrix has already been processed. Zeroing the first column early overwrites matrix[r][0], which is the row-marker — corrupting subsequent checks for inner cells. The correct order is: (1) zero inner cells, (2) zero first column if matrix[0][0] == 0, (3) zero first row if rowZero.