Set Matrix Zeroes — Editorial

Opening the reading…

Intuitionreuse the matrix as its own marker storage

A zero at position (i, j) affects exactly two things: every cell in row i and every cell in column j. You could record affected rows and columns in separate arrays, but the matrix already has one convenient cell in each row and column that can carry this information: matrix[i][0] marks row i, and matrix[0][j] marks column j.

The first row and first column create one collision. A zero in the first row should mark the entire first row, while matrix[0][j] is also being used as the marker for column j. The same collision occurs in the first column. Two Boolean flags preserve whether those boundary lines contained an original zero, so the matrix can safely serve as O(1)-space bookkeeping.

Approach

Scan the first row and set firstRowZero if it already contains a zero, because later writes to the top row will also serve as column markers and could otherwise erase this original fact.

Scan the first column and set firstColZero if it already contains a zero, because matrix[i][0] will later serve as the marker for row i.

Inspect only the interior cells, from row 1 and column 1 onward. For each original zero at (i, j), set matrix[i][0] and matrix[0][j] to zero; without this pass, the affected row and column would not be recorded.

Use the recorded markers to zero interior cells whose row marker or column marker is zero. Delaying this pass prevents newly written zeros from being mistaken for original zeros during discovery.

If firstRowZero is true, zero the entire first row, because its marker cells do not by themselves distinguish an original top-row zero from a marker written by an interior zero.

If firstColZero is true, zero the entire first column for the same reason; this final boundary pass also handles the top-left cell correctly.

Complexitythe matrix is scanned a constant number of times

MEASURE	BOUND	WHY
Time	O(m x n)	The interior is examined during the marking pass and the applying pass, while the boundary scans touch only O(m + n) cells. Each matrix cell is processed a constant number of times, so the total remains O(m x n).
Space	O(1) extra	Only two Boolean flags and a fixed number of indices are added beyond the matrix itself. The matrix is modified in place, so there is no returned array whose storage must be counted; the bound stays O(1) for every matrix shape.

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

Annotated solutionC++ · in-place marker passes · constant extra space

CPPMark affected rows and columns in the boundaries, then apply those markers to the interior.

#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool firstRowZero = false;
        bool firstColZero = false;

        for (int j = 0; j < n; ++j) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

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

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (firstRowZero) {
            for (int j = 0; j < n; ++j) {
                matrix[0][j] = 0;
            }
        }

        if (firstColZero) {
            for (int i = 0; i < m; ++i) {
                matrix[i][0] = 0;
            }
        }
    }
};

The order of the passes is the central insight. The first pass asks which cells were originally zero, while the second pass asks which cells must become zero. If you combine those jobs, a zero written during the solution process looks like an original zero and spreads farther than the statement requires.

The marker-array alternativesimpler bookkeeping, but not the required space bound

A straightforward alternative stores one Boolean per row and one per column. First scan the matrix and mark every row and column containing an original zero, then scan it again and clear cells whose row or column is marked. This is often easier to explain and debug, but it uses O(m + n) extra space instead of the required O(1), so the boundary-marker solution is the space optimisation rather than a different time strategy.

CPPThe clearer two-array version: record affected rows and columns before changing any cell.

#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> zeroRow(m, false);
        vector<bool> zeroCol(n, false);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    zeroRow[i] = true;
                    zeroCol[j] = true;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (zeroRow[i] || zeroCol[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};