Set Matrix Zeroes

Set Matrix Zeroes

What is this problem about?

The Set Matrix Zeroes interview question gives you an m×n matrix. If any element is 0, set its entire row and entire column to 0. The challenge is doing this in-place without using extra space to mark which rows and columns need to be zeroed — because naively spreading zeros during iteration would incorrectly zero cells that weren't originally 0.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this problem because it tests the ability to avoid O(m+n) auxiliary space by cleverly using the matrix itself as a marker board. The O(1) space solution uses the first row and first column as flags — a technique that requires careful handling of two special markers at the intersection (matrix[0][0]). It models in-place data transformation, a critical skill in embedded and memory-constrained systems.

Algorithmic pattern used

The pattern is in-place flagging using first row/column as markers. Two-pass algorithm: Pass 1 — scan the matrix for zeros. Use the first row and first column as markers: if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0. Use a separate boolean to track whether the first row itself needs zeroing (since matrix[0][0] is overloaded). Pass 2 — apply zeroing: for each cell (i, j) where i > 0, j > 0, if matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0. Then zero the first row/column based on the saved booleans.

Example explanation

Matrix:

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

Pass 1: matrix[1][1]=0 → mark matrix[1][0]=0 and matrix[0][1]=0.

Pass 2 (cells i>0, j>0):

• (1,1): matrix[1][0]=0 → zero entire row.
• (1,2): matrix[1][0]=0 → zero.
• (0,1): matrix[0][1]=0 → zero.

Result:

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

Common mistakes candidates make

• Zeroing rows and columns in the first pass while iterating — this causes cells that weren't originally 0 to become 0, incorrectly spreading the zeroing.
• Not handling matrix[0][0] specially — it's shared by the first-row marker and first-column marker, causing ambiguity.
• Using an O(m+n) set to track zero rows and columns — correct but uses extra space; the O(1) solution is expected at this level.
• Applying the second pass in the wrong order — zero the bulk cells first, then zero the first row/column based on saved flags.

Interview preparation tip

For the Set Matrix Zeroes coding problem, the matrix in-place array interview pattern is the core skill. The O(1) space solution with first-row/column flags is the expected answer at Goldman Sachs and Adobe. Practice walking through the two-flag edge case: matrix[0][0] marks the first column, but a separate first_row_zero boolean is needed for the first row. Interviewers test this exact intersection — internalize it before the interview. Draw the pass diagram on paper to avoid mixing up pass 1 (marking) and pass 2 (zeroing).