55. Set Matrix Zeroes
mediumAsked at WorkdayA zero anywhere in the grid wipes its full row and full column — and the matrix must be mutated in place, no second grid allowed. Workday candidates report this medium as a scratch-space discipline test: an HR platform's department-by-cost-center allocation grids make cascading deactivation a familiar shape, and the interviewer is watching whether you can borrow the matrix's own first row and column as flag storage without destroying the data those flags describe.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Workday loops.
- Glassdoor (2025)— Workday SDE2 phone screen.
- LeetCode (2026)— Problem #73 'Set Matrix Zeroes' — canonical statement, bounds, and the explicit constant-space follow-up.
Problem
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place — the constant-space refinement that reuses the matrix as its own bookkeeping is the stated follow-up.
Constraints
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1Follow-up: A straightforward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?
Examples
Example 1
matrix = [[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]Explanation: One central zero knocks out the middle row and middle column; the four corners are untouched because they share neither index with the zero.
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: Row 0 holds zeros at columns 0 and 3, so all of row 0 plus those two columns become zero — and double-wiping overlapping cells is harmless since zeroing is idempotent.
Approaches
1. Two sets
Find row/col indices to zero. Apply.
- Time
- O(m*n)
- Space
- O(m+n)
const zeroRows = new Set(), zeroCols = new Set();
for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (matrix[i][j]===0) { zeroRows.add(i); zeroCols.add(j); }
for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (zeroRows.has(i)||zeroCols.has(j)) matrix[i][j]=0;Tradeoff: Two clean passes and easy to verify, but the O(m+n) sets are pure bookkeeping — and the problem statement itself flags constant space as the real target. Write it first as your correctness checkpoint, then immediately offer the marker refinement unprompted.
2. Use first row/column as markers
Track whether row 0 or col 0 had any zeros via two booleans. Use row 0 and col 0 as marker storage. Apply zeros bottom-right to top-left.
- 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. The two booleans track whether row 0 / col 0 themselves had zeros so we don't accidentally lose that info when using them as markers.
Workday-specific tips
Workday candidates report the interview hinging on scratch-space reuse: the first row and column become the flag arrays, and the two booleans exist because those lines' OWN original zero-state gets overwritten the moment marking begins. State that dependency before coding, then narrate the pass order — capture booleans, mark interior zeros into the edges, wipe interior from the marks, settle the edges last. If the domain comes up, a cascading-deactivation analogy (disable a department, blank its row and cost-center column) lands naturally for an HR-systems interviewer.
Common mistakes
- Forgetting the two booleans for the first row/column.
- Applying zeros to row 0 and col 0 during the marker phase — corrupts the markers.
- Iterating from 0 instead of 1 in the marker phase — same issue.
Follow-up questions
An interviewer at Workday may pivot to one of these next:
- Game of Life (LC 289) — same in-place encoding idea.
- Set Matrix Zeroes with negative numbers as flags.
- What if you can't write to row 0 or col 0?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why two booleans instead of one?
matrix[0][0] is shared between row 0 and col 0. If you used it as a single marker, you couldn't distinguish 'first row had a zero somewhere' from 'first column had a zero somewhere'.
Why apply markers bottom-up?
Order doesn't strictly matter, but applying inside-out (i,j >= 1 first) preserves the markers in row 0 / col 0 until last.
Why can't a sentinel value like -1 replace the marker rows?
The value range spans the full 32-bit integer space, so any sentinel you pick could legitimately appear in the data and be misread as a flag. The first-row/column trick avoids sentinels entirely by spending positions, not values.