Skip to main content

57. Set Matrix Zeroes

mediumAsked at Snowflake

If an element is 0, set its entire row and column to 0, in place. Snowflake asks this to test in-place state propagation using existing storage as flags — same idea as encoding null bitmaps inline with column data.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake storage-team uses this in onsites.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-I screens.

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

First pass: collect row indices and column indices that contain zero. Second pass: zero them out.

Time
O(mn)
Space
O(m+n)
function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  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: O(m+n) extra space. Works, but doesn't satisfy the follow-up.

2. Use first row and first column as flags (optimal)

Use row 0 as the 'this column has a 0' flag and column 0 as the 'this row has a 0' flag. Save a separate flag for row 0 and column 0 themselves. Update in two passes.

Time
O(mn)
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 — uses existing matrix cells as flag storage. The exact trick used to store null bitmaps inline in columnar formats.

Snowflake-specific tips

Snowflake interviewers want the O(1)-space follow-up nailed. Bonus signal: connect to inline null bitmaps — Parquet (which Snowflake reads/writes) stores null flags inline with column data exactly to avoid a separate bitmap allocation.

Common mistakes

  • Forgetting separate flags for row 0 and column 0 themselves — they get clobbered during the marker phase.
  • Doing the zero-out before reading all flags — corrupts the markers.
  • Off-by-one on the inner loops (must start at i=1, j=1).

Follow-up questions

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

  • What if matrix is sparse? — keep zero-row and zero-col sets only.
  • Generalize to 'if element matches X, zero its row and column'.
  • How do columnar formats encode null bitmaps?

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 firstRowZero and firstColZero separately?

Once you start using row 0 and column 0 as flag storage, you've overwritten any zeros originally in row 0 or column 0. The flags must be saved before the marker phase corrupts them.

Why is this related to null bitmaps?

Both reuse existing storage to encode metadata. Parquet packs null indicators inline with data; this problem packs 'should zero' indicators in the first row and column.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →