73. Set Matrix Zeroes
mediumAsked at CanvaZero out entire rows and columns wherever a zero appears, without allocating a second matrix — Canva candidates report this as a test of in-place mutation discipline, a natural fit for a design tool whose layout grids are memory-sensitive at large canvas sizes. The interview ladder is predictable: the O(m+n) tracking-set version proves correctness, then the real question lands — do it again in O(1) extra space using the matrix itself as scratch storage.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Canva loops.
- LeetCode (2026)— Problem #73 'Set Matrix Zeroes' — canonical statement, bounds, and the explicit O(1)-space follow-up.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Canva interview prep.
Problem
Given an m×n integer matrix, if any element is 0, set its entire row and entire column to 0. You must do it in-place. Follow-up: can you achieve O(1) extra space?
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: matrix[1][1] is 0, so row 1 and column 1 are zeroed.
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]]Approaches
1. Brute force (Set tracking)
Record which rows and columns contain a zero, then zero them out in a second pass.
- Time
- O(m*n)
- Space
- O(m+n)
function setZeroes(matrix) {
const rows = new Set();
const cols = new Set();
const m = matrix.length;
const n = matrix[0].length;
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: Two clean passes and impossible to get wrong, but the O(m+n) sets exist purely as bookkeeping — and this problem is famous for the follow-up that takes them away. Treat it as your correctness checkpoint, not your answer.
2. Optimal (use first row/col as markers)
Use the first row and first column as sentinel arrays to record zero positions, handling their own zero-presence with two boolean flags — O(1) extra space.
- Time
- O(m*n)
- Space
- O(1)
function setZeroes(matrix) {
const m = matrix.length;
const n = matrix[0].length;
let firstRowZero = matrix[0].includes(0);
let firstColZero = false;
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) firstColZero = true;
}
// Use first row/col as markers
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;
}
}
}
// Zero out interior based on markers
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;
}
}
// Zero first row/col if needed
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: Constant extra space by storing flags in row 0 and column 0 themselves. The cost is strict pass ordering — capture the edges' own zero state first, mark, wipe interior, wipe edges last — because the markers live inside the data they describe.
Canva-specific tips
Canva interviewers flag candidates who jump straight to the O(m+n) set approach without considering the O(1) follow-up — the design-tool codebase is memory-sensitive when working with large canvases. Walk through why the first row/column trick works: they act as free scratch space as long as you capture their own zero-status before overwriting. The interview typically ends with 'can you do it without extra space?' — anticipate this and mention the two-boolean sentinel approach before you're asked.
Common mistakes
- Zeroing cells during the discovery scan — fresh zeros become indistinguishable from original ones and cascade across the whole matrix.
- Wiping row 0 or column 0 before the interior pass — that destroys the markers while they are still being read.
- Forgetting that matrix[0][0] sits in BOTH marker lines — it needs the two separate boolean flags, not the shared cell.
- Using a sentinel value like -1 as the marker — the value range spans all 32-bit integers, so any sentinel can collide with legitimate data.
Follow-up questions
An interviewer at Canva may pivot to one of these next:
- Game of Life (LC 289): the same encode-two-states-in-place trick where every cell must transition simultaneously.
- Rotate Image (LC 48): the companion in-place matrix problem where pass ordering is again the entire difficulty.
- How would the approach change for a sparse matrix stored as coordinate tuples instead of a dense grid?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why can't I zero rows and columns as I discover zeros?
Because written zeros are indistinguishable from original zeros — each new zero would trigger further wipes and most inputs collapse to an all-zero matrix. Discovery and writing must be separate phases.
Why do the two boolean flags exist?
Row 0 and column 0 double as marker storage, so their own original zero state gets overwritten by markers. Capturing 'did row 0 / column 0 contain a real zero?' up front is the only way to settle them correctly at the end.
Is the O(m+n) version a failing answer?
No — it is the right first answer, and it passes the judge. It becomes a failing answer only if you cannot then produce the O(1) refinement when asked, which is the actual point of the question.