Skip to main content

55. Set Matrix Zeroes

mediumAsked at Plaid

If an element in an MxN matrix is 0, zero out its entire row and column in-place. Plaid asks this because invalidating a row+column band of a cached pivot table when one cell flips is exactly this primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid platform OA.
  • LeetCode Discuss (2026)— Plaid in-place matrix problem.

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. 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?

Constraints

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

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 arrays for rows and cols

First pass marks zero rows and cols. Second pass writes zeros.

Time
O(mn)
Space
O(m+n)
function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const zRow = new Set(), zCol = new Set();
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (matrix[i][j] === 0) { zRow.add(i); zCol.add(j); }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (zRow.has(i) || zCol.has(j)) matrix[i][j] = 0;
}

Tradeoff: O(m+n) space. Acceptable; the constant-space variant is the bonus.

2. Use first row and column as markers

Record whether the first row and first column themselves should be zeroed. Then use them as flags for the rest of the matrix.

Time
O(mn)
Space
O(1)
function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let row0 = false, col0 = false;
  for (let j = 0; j < n; j++) if (matrix[0][j] === 0) row0 = true;
  for (let i = 0; i < m; i++) if (matrix[i][0] === 0) col0 = 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 (row0) for (let j = 0; j < n; j++) matrix[0][j] = 0;
  if (col0) for (let i = 0; i < m; i++) matrix[i][0] = 0;
}

Tradeoff: Constant space. The first row and column do double duty: they are both data and markers. The two booleans capture whether they themselves should be zeroed.

Plaid-specific tips

Plaid grades this on whether you can hit O(1) space. Bonus signal: discuss the order — must mark before zeroing, must zero the first row/column LAST so we don't lose the marker info. Connect to cache invalidation where a single 0 cell triggers a row+column band invalidation.

Common mistakes

  • Marking and zeroing in the same pass — corrupts later markings.
  • Forgetting to handle the first row/column separately — using them as markers means we can't trust their original values.
  • Zeroing the first row/column too early — wipes out the markers.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Maintain a persistent zero-mask for streaming updates.
  • Zero out diagonally adjacent cells too.
  • Generalize to 3D tensors.

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 save row0 and col0 separately?

Because we're using the first row and column as markers, we lose their original meaning. The two booleans preserve whether they originally contained any zero.

Why zero the markers last?

If we zero the first row early, all subsequent column-marker checks see a zero — incorrectly zeroing cells that shouldn't be.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →