{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Set Matrix Zeroes – Solution & Complexity

Interview solutions
/
Set Matrix Zeroes

Solution Walkthrough

1. Understanding the problem

  • A single 0 anywhere in the matrix wipes out its whole row and its whole column.
  • The tricky part is not overwriting a cell to 0 and then mistakenly treating that new 0 as if it were an original zero later in the scan.

2. Brute-force with an extra copy

  • Make a copy of the original matrix so zeroing decisions are always based on the untouched values.
  • Scan the copy for zeros, and zero the corresponding row/column in the real matrix.
  • Uses O(m*n) extra space, but is simple and clearly correct.
def set_zeroes(matrix):
    if not matrix or not matrix[0]:
        return matrix
    rows = len(matrix)
    cols = len(matrix[0])
    original = [row[:] for row in matrix]
    for r in range(rows):
        for c in range(cols):
            if original[r][c] == 0:
                for k in range(cols):
                    matrix[r][k] = 0
                for k in range(rows):
                    matrix[k][c] = 0
    return matrix

3. Reduce space with row/column marker sets

  • Instead of copying the whole matrix, do one pass to record which row indices and column indices contain a zero.
  • Then do a second pass and zero any cell whose row or column was recorded.
  • This drops space from O(m*n) to O(m + n).
def set_zeroes(matrix):
    if not matrix or not matrix[0]:
        return matrix
    rows = len(matrix)
    cols = len(matrix[0])
    zero_rows = set()
    zero_cols = set()
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                zero_rows.add(r)
                zero_cols.add(c)
    for r in range(rows):
        for c in range(cols):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0
    return matrix

4. Dry run / state trace

Trace matrix = [[1,0],[0,1]].

stepactionzero_rowszero_cols
scan (0,1)value is 0{0}{1}
scan (1,0)value is 0{0,1}{0,1}

Second pass: every row is in zero_rows and every column is in zero_cols, so all four cells become 0, giving [[0,0],[0,0]].

5. Common mistakes and follow-ups

  • Zeroing cells while still scanning for the original zeros, which turns freshly-zeroed cells into false positives for later iterations.
  • Forgetting the empty-matrix guard before indexing matrix[0].
  • Follow-up: the true O(1) extra-space version reuses matrix[0] and the first column as the marker arrays themselves, with one extra boolean to remember whether the first row/column originally had a zero — worth mentioning even though this judge's tests only check the returned values, not memory usage.

6. Edge cases to test mentally

  • A 1x1 matrix with either a zero or non-zero value.
  • A matrix with no zero at all (must be returned unchanged).
  • A matrix where every row and column ends up zeroed.
  • Negative values mixed with a single zero.

7. Final full solution and complexity

Record zero rows/columns in a first pass, then zero matching cells in a second pass. Time is O(m*n), and extra space is O(m + n) for the marker sets.

def set_zeroes(matrix: list[list[int]]) -> list[list[int]]:
    if not matrix or not matrix[0]:
        return matrix

    rows = len(matrix)
    cols = len(matrix[0])
    zero_rows = set()
    zero_cols = set()

    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                zero_rows.add(r)
                zero_cols.add(c)

    for r in range(rows):
        for c in range(cols):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0

    return matrix

FAQ

See also

Practice Set Matrix Zeroes online (run code in the browser)Rotate Image solution (medium)Search a 2D Matrix solution (medium)Spiral Matrix solution (medium)Spiral Matrix II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?