Skip to main content

19. Set Matrix Zeroes

mediumAsked at Unity

Zero out entire rows and columns for any cell that holds zero — identical to the clear-channel propagation Unity's render pipeline uses when a render texture pixel flags its entire row and column of tiles for invalidation.

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

Problem

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. Do this in-place.

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. Extra sets for rows and columns

Scan matrix once; record zero-rows and zero-cols in two Sets. Scan again to zero those rows and columns.

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

2. O(1) space using first row and column as markers

Use the first row and first column as sentinel arrays. Handle first-row and first-column zeroing separately with two boolean flags.

Time
O(m*n)
Space
O(1)
function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let firstRowZero = matrix[0].includes(0);
  let firstColZero = matrix.some(r => r[0] === 0);
  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) matrix[0].fill(0);
  if (firstColZero) { for (let i = 0; i < m; i++) matrix[i][0] = 0; }
}

Tradeoff:

Unity-specific tips

Unity values the O(1)-space solution here because GPU memory is precious — frame interviewers as if you're minimizing auxiliary allocations in a render pass, and explicitly call out why you guard the first-row sentinel separately.

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 Unity interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →