Skip to main content

56. Set Matrix Zeroes

mediumAsked at Reddit

If an element in an m x n matrix is 0, zero out its entire row and column. Reddit uses this to test in-place 2D manipulation under a tight memory budget — the same shape they'd use to scrub rows/columns of an analytics matrix when a user is GDPR-deleted.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common in-place medium.

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 straight forward 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. Track rows/cols in sets

First pass: collect row indices and col indices of zeros. Second pass: zero them.

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

Tradeoff: O(m+n) extra. Fails the follow-up's O(1) goal.

2. First row/col as markers (optimal)

Use matrix[0][j] and matrix[i][0] to mark whether row i / col j has a zero. Special-flag first row/col separately to avoid self-clobbering.

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

Tradeoff: O(1) extra. The classic interview trick: encode state in unused regions of the input itself.

Reddit-specific tips

Reddit interviewers grade on the in-place encoding insight. Bonus signal: explain WHY you must track the first row and column with separate flags — using them as markers would self-clobber.

Common mistakes

  • Modifying as you go (zeros propagate and the whole matrix becomes 0).
  • Forgetting the special flags for the first row and column.
  • Iterating from 0 in the second pass (overwrites the marker row/col before applying).

Follow-up questions

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

  • Game of Life (LC 289) — similar in-place encoding.
  • Spiral matrix (LC 54).
  • Sparse matrix multiplication (LC 311).

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 separate flags?

The first row's matrix[0][j] is the col marker; we can't use the same cell for the row's marker. So matrix[0][0] would conflict, hence the two flags.

What if the matrix contains 0 deliberately (not marking)?

Our markers ARE 0s. That's fine because we only zero cells when their marker is 0, and any pre-existing 0 was already going to mark.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →