Set Matrix Zeroes

You are given an m x n grid of integers called matrix. Wherever the grid originally contains a 0, every cell in that zero's row and every cell in its column must become 0.

Change matrix in place; your function does not return anything. Zeros that you write while processing must not trigger further wiping: only the zeros present in the input count.

Example 1

Example 2

Example 3

Constraints

• m == matrix.length, n == matrix[i].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

Pattern Path · Hashing & Counting · problem 12 of 169

Start simple

Copy the whole grid, then for every zero in the copy wipe its row and column in the original: O(m·n·(m + n)) time and O(m·n) space.

The key idea

The answer depends only on which rows and which columns held a zero, not on individual cells. So the job splits into two passes: record the rows and columns to clear, then clear them.

Recording needs one flag per row and one per column. Instead of allocating new arrays, borrow the grid's first column for the row flags and its first row for the column flags: when matrix[r][c] == 0, set matrix[r][0] and matrix[0][c] to 0. Those cells are going to become 0 anyway, so overwriting them loses nothing.

One conflict remains: the first row and first column now hold flags, so you can no longer tell whether they had zeros of their own. Check that with two booleans before marking. Then clear the inner cells using the flags, and finally clear row 0 and column 0 if their booleans say so. Doing the edges last matters, because clearing them first would destroy the flags you still need.

Complexity

• Time: O(m · n)
• Space: O(1)

Python

class Solution:
    def setZeroes(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        # Row 0 and column 0 will hold the markers, so record their own state first.
        first_row_has_zero = any(matrix[0][c] == 0 for c in range(cols))
        first_col_has_zero = any(matrix[r][0] == 0 for r in range(rows))

        # Mark: a zero at (r, c) flags row r in column 0 and column c in row 0.
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0

        # Clear inner cells whose row or column is flagged.
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0

        # Finally handle the marker row and column themselves.
        if first_row_has_zero:
            for c in range(cols):
                matrix[0][c] = 0
        if first_col_has_zero:
            for r in range(rows):
                matrix[r][0] = 0

JavaScript

var setZeroes = function(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  // Row 0 and column 0 will hold the markers, so record their own state first.
  const firstRowHasZero = matrix[0].some(v => v === 0);
  const firstColHasZero = matrix.some(row => row[0] === 0);

  // Mark: a zero at (r, c) flags row r in column 0 and column c in row 0.
  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;
        matrix[0][c] = 0;
      }
    }
  }

  // Clear inner cells whose row or column is flagged.
  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
  }

  // Finally handle the marker row and column themselves.
  if (firstRowHasZero) matrix[0].fill(0);
  if (firstColHasZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
};

What the interviewer is checking

The interviewer wants to see you notice the "fresh zero vs original zero" trap, then push from O(m + n) memory to O(1) by reusing the input as scratch space.

Mistakes to avoid

• Zeroing cells during the scan, so new zeros spread and wipe the whole grid.
• Forgetting that row 0 and column 0 double as marker storage, then losing whether they originally contained a zero.
• Clearing the first row or column before using the markers stored in them.
• Sharing one flag for matrix[0][0], which belongs to both the first row and the first column.

Follow-ups to expect

• What if the grid is too large to fit in memory? (Stream rows; keep column flags only.)
• Can you do it in a single pass? (No: originals must be known first.)
• What if a cell should clear only its row? (Row flags only, one pass.)

In real software

Spreadsheet and data-cleaning tools apply the same idea when one invalid cell must invalidate an entire record and an entire field, and they reuse header cells as bookkeeping to avoid extra memory.

Practice next