Skip to main content

73. Set Matrix Zeroes

mediumAsked at Canva

Zero out entire rows and columns wherever a zero appears — Canva uses this to test in-place mutation discipline, mirroring how their grid-layout engine propagates empty-cell constraints without allocating a second matrix.

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

Problem

Given an m×n integer matrix, if any element is 0, set its entire row and entire column to 0. You must do it in-place. Follow-up: can you achieve O(1) extra space?

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]]

Explanation: matrix[1][1] is 0, so row 1 and column 1 are zeroed.

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. Brute force (Set tracking)

Record which rows and columns contain a zero, then zero them out in a second pass.

Time
O(m*n)
Space
O(m+n)
function setZeroes(matrix) {
  const rows = new Set();
  const cols = new Set();
  const m = matrix.length;
  const n = matrix[0].length;
  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:

2. Optimal (use first row/col as markers)

Use the first row and first column as sentinel arrays to record zero positions, handling their own zero-presence with two boolean flags — O(1) extra space.

Time
O(m*n)
Space
O(1)
function setZeroes(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  let firstRowZero = matrix[0].includes(0);
  let firstColZero = false;
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) firstColZero = true;
  }
  // Use first row/col as markers
  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;
      }
    }
  }
  // Zero out interior based on markers
  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;
    }
  }
  // Zero first row/col if needed
  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:

Canva-specific tips

Canva interviewers flag candidates who jump straight to the O(m+n) set approach without considering the O(1) follow-up — the design-tool codebase is memory-sensitive when working with large canvases. Walk through why the first row/column trick works: they act as free scratch space as long as you capture their own zero-status before overwriting. The interview typically ends with 'can you do it without extra space?' — anticipate this and mention the two-boolean sentinel approach before you're asked.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →