Set Matrix Zeroes — O(1) Space In-Place Trick

The Problem

You are given an m x n integer matrix. If a cell is 0, set every cell in its row and column to 0. Modify the matrix in place. The follow-up asks for O(1) extra space.

The naive approach allocates a copy. The clever approach reuses the matrix itself to record which rows and columns must be zeroed.

Intuition

Reuse the first row and first column of the matrix as marker arrays. When a cell (i, j) with i, j > 0 is zero, write a 0 to matrix[i][0] and matrix[0][j]. Later, when zeroing the interior, look those markers up.

The catch: the first row and first column themselves might need to be zeroed, and once you start overwriting them you lose the ability to distinguish original zeros from markers you wrote. So you cache that information in two boolean flags before the marker pass begins. Three phases total: (1) record whether row 0 or column 0 originally contain a zero; (2) scan the interior and write markers; (3) apply markers to zero the interior, then apply the cached flags to row 0 and column 0.

Explanation with Example

Take this 3x4 matrix:

[1, 1, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 0]

First-row-zero: false. First-col-zero: false. After the marker phase the matrix looks like:

[1, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 1, 0]

After zeroing the interior using markers:

[1, 0, 1, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]

The first row stays [1, 0, 1, 0] because the original first row had no zero — only the markers we wrote remain.

input:
[1, 1, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 0]

after marking:
[1, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 1, 0]

after zeroing interior:
[1, 0, 1, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]

flags: first_row_zero=False, first_col_zero=False
final = above

Code

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))

    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;

    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;
}

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRowZero = false, firstColZero = false;
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;

    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;
}

Edge Cases

A matrix where the first row contains a zero needs the flag, otherwise after marking we cannot distinguish original zeros from markers we wrote. Same for the first column. A matrix of all zeros stays all zeros. A matrix with no zeros is unchanged.

A 1xN or Mx1 matrix is fine because the loops over range(1, m) or range(1, n) just don’t execute, and the flag-based final pass handles everything.

Complexity Analysis

Time is O(mn): three passes over the matrix, each O(mn). Space is O(1) extra — just the two boolean flags. The first row and column are reused, not duplicated.

This is the only solution with strictly constant extra space. The two-marker-array version is O(m + n), which is sometimes mistaken for O(1) but is not.

How to Explain It in an Interview

Frame the trick clearly: “I’ll use the first row and first column to remember which rows and columns must be zeroed. I keep two boolean flags for the first row and first column themselves, because once I start overwriting them I’ll lose that information.” Then walk through the three phases on a small 3x3.

Mention up front that this is a classic example of using the input as auxiliary state. Interviewers love seeing that.

If asked why two flags rather than one, point out that the first row and first column are independent: one might need zeroing and the other not. Both must be tracked.

Related Problems

• Rotate Image — in-place matrix transformation.
• Spiral Matrix — careful index discipline on 2D arrays.
• Valid Sudoku — bitmask tracking by row/col.
• Game of Life — in-place state update on a grid.