57. Set Matrix Zeroes
mediumAsked at OlaSet Matrix Zeroes hands you an m x n grid and one rule: wherever a zero sits, its whole row and column become zeros — and you must do it in place. Ola candidates report it as a space-optimization ladder: interviewers accept the O(m+n) tracking-set answer, then immediately ask for O(1) extra space, which forces the first-row-and-column marker trick and exposes whether you can mutate state you are still reading from without corrupting it.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Ola loops.
- LeetCode (2026)— Problem #73 'Set Matrix Zeroes' — canonical statement, the 1 <= m, n <= 200 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 Ola interview prep.
Problem
Given an m x n integer matrix, if an element is 0, set its entire row and column to 0s. You must do it in place. A straightforward O(m+n)-space solution exists — the real ask is the constant-space version that reuses the matrix itself as its own bookkeeping.
Constraints
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1 — values can be anything, so you cannot use a magic sentinel number as a marker.
Examples
Example 1
matrix = [[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,1,1]] -> [[1,0,1],[0,0,0],[1,0,1]]Explanation: The single zero at row 1, column 1 wipes its full row and full column; everything else is 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: Two zeros in row 0 (columns 0 and 3) zero out row 0 entirely plus both columns — overlapping wipes are fine because zeroing is idempotent.
Approaches
1. Track row/col sets
Record rows and cols that contain a zero; zero them in a second pass.
- Time
- O(m*n)
- Space
- O(m+n)
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: Correct, readable, and the right thing to write first — but it spends O(m+n) memory purely on bookkeeping, and this problem is famous precisely because the interviewer's next sentence is 'now do it without the sets'.
2. First row/col as markers
Use the matrix's own first row/col as the zero-flags; track first row/col separately and apply at the end.
- Time
- O(m*n)
- Space
- O(1)
function setZeroes(m) {
const R = m.length, C = m[0].length;
let r0 = false, c0 = false;
for (let j = 0; j < C; j++) if (m[0][j] === 0) r0 = true;
for (let i = 0; i < R; i++) if (m[i][0] === 0) c0 = true;
for (let i = 1; i < R; i++) for (let j = 1; j < C; j++) if (m[i][j] === 0) { m[i][0] = 0; m[0][j] = 0; }
for (let i = 1; i < R; i++) for (let j = 1; j < C; j++) if (m[i][0] === 0 || m[0][j] === 0) m[i][j] = 0;
if (r0) for (let j = 0; j < C; j++) m[0][j] = 0;
if (c0) for (let i = 0; i < R; i++) m[i][0] = 0;
}Tradeoff: Constant extra space by storing the flags inside row 0 and column 0 themselves. The price is ordering discipline: interior cells first, the flag row/column last — invert that order and your markers wipe the data they were guarding.
Ola-specific tips
Ola candidates report the in-place marker trick as the expected destination, with the interview really testing whether you process cells in an order that never destroys unread bookkeeping. If the conversation goes domain-ward, a ride-hailing grid gives a natural analogy: when one cell of a zone matrix invalidates (a surge rule, an offline driver), you want to flag the whole row and column compactly without allocating a second grid. Walk the marker order out loud — scan, mark in first row/col, apply interior, apply edges last.
Common mistakes
- Zeroing rows and columns DURING the first scan — newly written zeros then trigger more wipes and cascade across the matrix.
- Applying the first row/column flags before the interior cells — you erase the markers you still need to read.
- Forgetting the two separate booleans for whether row 0 and column 0 themselves contained an original zero.
- Using a sentinel value like -1 as a marker — the value range covers all 32-bit integers, so any sentinel can collide with real data.
Follow-up questions
An interviewer at Ola may pivot to one of these next:
- Game of Life (LC 289): the same in-place state-encoding trick, but every cell transitions simultaneously — encode old+new state in one int.
- Rotate Image (LC 48): another in-place matrix mutation where operation ordering is the entire difficulty.
- What changes if the matrix is sparse and stored as a list of (row, col, value) entries 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 just zero things as I find them?
Because written zeros become indistinguishable from original zeros — the cascade wipes the whole matrix in most inputs. Separating the discovery pass from the write pass is the core of the problem.
Why use the first row and column as flag storage?
Every cell (i, j) already intersects row 0 at (0, j) and column 0 at (i, 0), so those two lines form a natural index of which rows and columns must be wiped — free storage that needs no allocation.
Is O(1) extra space actually required to pass?
The O(m+n) set version passes the judge, but the problem statement explicitly frames constant space as the follow-up — in interviews the set version is your correctness checkpoint, not your final answer.