Skip to main content

55. Set Matrix Zeroes

mediumAsked at Workday

If an element is 0, set its entire row and column to 0 in place. Workday uses this for in-place matrix updates with marker tricks — same shape as cascading deactivation of a department in a 2D allocation grid.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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.

Constraints

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1
  • Follow-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

Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]

Example 2

Input
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

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: O(m+n) space. Fails the follow-up.

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 is testing whether you can re-use the matrix as scratch space. The two booleans for row 0 / col 0 are the trick — without them, you'd zero the markers based on the data they store. State this before coding.

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Set Matrix Zeroes and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →