Skip to main content

55. Set Matrix Zeroes

mediumAsked at Datadog

Given an m x n matrix, if an element is 0, set its entire row and column to 0 — in place, O(1) extra space. Datadog asks this for the encode-state-in-matrix trick — same shape as their in-place chunk-level invalidation marks during compaction.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite in-place mutation.

Problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place. A straightforward solution using O(m * n) 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 boolean arrays

rows[] and cols[] mark which rows/cols contain a 0. Second pass zeros them out.

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

Tradeoff: O(m+n) space. Datadog will push for O(1).

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

Use matrix[0][...] and matrix[...][0] as flags. Track whether row 0 and col 0 originally had zeros separately.

Time
O(m * n)
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. The trick is using the first row/col as the marker array, with two extra flags for the row/col themselves. Datadog-canonical.

Datadog-specific tips

Datadog grades on the in-place encoding insight. Articulate why you need TWO extra flags (firstRowZero, firstColZero) — because the first row and column are doing double duty as both data and marker storage.

Common mistakes

  • Forgetting the two flag variables — corrupts the first row and column.
  • Iterating from (0, 0) in the marker pass instead of (1, 1) — would overwrite marker rows.
  • Setting the first row/col to 0 BEFORE the second pass — corrupts the markers.

Follow-up questions

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

  • Set Matrix Diagonals to Zero — variant.
  • Game of Life (LC 289) — same in-place encoding trick.
  • Datadog-style: in-place chunk invalidation marking.

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

The first row stores markers for columns; the first column stores markers for rows. If we don't track their original state, we can't tell whether they should be zeroed because they originally had a zero, or just because they hold markers.

Why iterate from (1,1) for the marker pass?

(0, 0) is reserved as a marker storage. Iterating from (1,1) for both reading and writing keeps markers consistent.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →