55. Set Matrix Zeroes
mediumAsked at VercelIf an element in an m x n matrix is 0, set its entire row and column to 0 — in place. Vercel candidates report this medium specifically for the O(1)-extra-space follow-up: the first row and column become your marker storage, which means their own original state must be captured before the markers clobber it. The four-pass ordering, not the idea, is where candidates fail.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Vercel loops.
- Glassdoor (2025-Q4)— Vercel platform onsite; O(1) space is the bonus.
- Blind (2026-Q1)— Listed in Vercel platform engineer screen.
Problem
Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place. The O(m+n)-space flag version is the warm-up; the expected destination is constant extra space using the matrix itself as bookkeeping.
Constraints
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1
Examples
Example 1
matrix = [[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]Explanation: The single zero at the center wipes row 1 and column 1; the four corner values survive untouched.
Example 2
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]][[0,0,0,0],[0,4,5,0],[0,3,1,0]]Explanation: Zeros at row 0, columns 0 and 3 wipe the entire first row plus both columns — overlapping wipes are safe because zeroing is idempotent.
Approaches
1. Two extra arrays for row/col flags
Mark rows and columns to zero in O(m+n) extra arrays; second pass zeros them.
- Time
- O(m*n)
- Space
- O(m+n)
function setZeroes(matrix) {
const m = matrix.length, n = matrix[0].length;
const rows = new Set(), cols = new Set();
for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (matrix[i][j] === 0) { rows.add(i); cols.add(j); }
for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (rows.has(i) || cols.has(j)) matrix[i][j] = 0;
}Tradeoff: O(m+n) extra space spent purely on bookkeeping — correct and readable, but this problem is famous precisely for the follow-up that takes the sets away. Write it first as the correctness checkpoint, then optimize.
2. Use first row/column as markers (optimal)
Use row 0 and col 0 to flag which rows/cols should be zeroed. Track separately whether row 0 / col 0 themselves should be zeroed. Two passes.
- Time
- O(m*n)
- Space
- O(1)
function setZeroes(matrix) {
const m = matrix.length, n = matrix[0].length;
let firstRowZero = false, firstColZero = false;
for (let j = 0; j < n; j++) if (matrix[0][j] === 0) firstRowZero = true;
for (let i = 0; i < m; i++) if (matrix[i][0] === 0) firstColZero = true;
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) { matrix[i][0] = 0; matrix[0][j] = 0; }
}
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
}
}
if (firstRowZero) for (let j = 0; j < n; j++) matrix[0][j] = 0;
if (firstColZero) for (let i = 0; i < m; i++) matrix[i][0] = 0;
}Tradeoff: O(1) extra space. Two boolean variables to remember whether row 0 / col 0 had a zero originally — these get overwritten by the marker storage, so they must be saved first.
Vercel-specific tips
Vercel candidates report the O(1) version is what gets graded, and the bonus signal is explaining WHY the two separate booleans exist: row 0 and column 0 are the marker storage, so their own original zero state gets clobbered and must be captured up front. Narrate the four-pass order explicitly — capture edge state, mark interior zeros into the edges, apply interior wipes, apply edge wipes last — because inverting any two of those passes corrupts the markers while they are still being read.
Common mistakes
- Forgetting the firstRowZero / firstColZero capture — overwrites the markers with the actual zeros.
- Doing the second pass without skipping row/col 0 — zeros propagate incorrectly.
- Mixing up the marker dimensions — row 0 marks columns, col 0 marks rows.
Follow-up questions
An interviewer at Vercel may pivot to one of these next:
- Game of Life (LC 289) — similar in-place flag pattern.
- What if 0 itself is a valid stored value? Use a sentinel.
- Set Matrix Ones — zero out everything except cells in a row/col with a 1.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why two extra booleans?
Row 0 and col 0 serve as the marker storage. If we just looked at matrix[0][j] at the end, we wouldn't know if that 0 was original (zero the whole row 0) or a marker (zero only column j).
Could I use Number.MIN_SAFE_INTEGER as a sentinel?
Yes, if the problem guarantees that value never appears. But the first-row/col trick uses no sentinel and works universally.
Why must the interior cells be processed before row 0 and column 0?
Row 0 and column 0 hold the flags the interior pass reads. Wiping them first destroys the very markers that say which rows and columns need zeroing — the edges must always be applied last.