Set Matrix Zeroes

How it works

We need to set an entire row and column to 0 if any cell in that row or column is 0.

The common two-array solution uses extra space to remember which rows/columns should be zeroed. To optimize space, we can reuse the matrix itself as the "marker storage":

• Use the first row to mark which columns should become zero
• Use the first column to mark which rows should become zero

One complication:

• matrix[0][0] sits at the intersection of the first row and first column, so it can't independently represent both.
• Also, we must separately track whether the first row originally contained a zero.

That's why we keep a boolean rowZero:

• rowZero = true means the first row must be zeroed at the end.

Steps

1. Initialize rowZero = false.
2. First pass (mark rows and columns):
   • Traverse every cell (r, c):
     • If matrix[r][c] == 0:
       • mark the column by setting matrix[0][c] = 0
       • if r > 0, mark the row by setting matrix[r][0] = 0
       • if r == 0, set rowZero = true (first row needs to be zeroed)
3. Second pass (apply markers to the inner matrix):
   • For r from 1 to ROWS - 1:
     • For c from 1 to COLS - 1:
       • If matrix[0][c] == 0 or matrix[r][0] == 0, set matrix[r][c] = 0
4. Handle the first column:
   • If matrix[0][0] == 0, zero out the entire first column
5. Handle the first row:
   • If rowZero is true, zero out the entire first row

Complexity

• Time complexity: O(m * n)
• Space complexity: O(1)

Where m is the number of rows and n is the number of columns.

Things to watch for

Modifying the Matrix While Scanning

Setting cells to zero while still scanning causes cascading updates where newly created zeros trigger more rows and columns to be zeroed. This produces incorrect results because the algorithm cannot distinguish between original zeros and zeros created during processing.

Forgetting to Track the First Row Separately

In the space-optimized approach, matrix[0][0] serves double duty for marking both the first row and first column. Using a single variable to track both leads to incorrect results. A separate boolean is needed to track whether the first row originally contained a zero.

Incorrect Order of Final Updates

When using the first row and column as markers, the order of applying updates matters. If you zero the first row or column too early, you lose the marker information needed to process the rest of the matrix. Always update the inner cells first, then handle the first row and column last.

from typing import List

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        ROWS, COLS = len(matrix), len(matrix[0])
        rowZero = False

        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0
                    if r > 0:
                        matrix[r][0] = 0
                    else:
                        rowZero = True

        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0

        if matrix[0][0] == 0:
            for r in range(ROWS):
                matrix[r][0] = 0

        if rowZero:
            for c in range(COLS):
                matrix[0][c] = 0

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        bool rowZero = false;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (matrix[r][c] == 0) {
                    matrix[0][c] = 0;
                    if (r > 0) {
                        matrix[r][0] = 0;
                    } else {
                        rowZero = true;
                    }
                }
            }
        }

        for (int r = 1; r < ROWS; r++) {
            for (int c = 1; c < COLS; c++) {
                if (matrix[0][c] == 0 || matrix[r][0] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }

        if (matrix[0][0] == 0) {
            for (int r = 0; r < ROWS; r++) {
                matrix[r][0] = 0;
            }
        }

        if (rowZero) {
            for (int c = 0; c < COLS; c++) {
                matrix[0][c] = 0;
            }
        }
    }
};