1 / 2
01A/191
Set Matrix Zero
Problem Statement

Given an m x n matrix, if any cell contains 0, set its complete row and complete column to 0. Return the final matrix after applying all such updates. In interviews, always clarify whether extra space is allowed or whether the matrix must be modified in-place.

Examples

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output: [[1,0,1],[0,0,0],[1,0,1]]

Explanation: Since matrix[1][1] is 0, row 1 and column 1 become 0.

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

Explanation: Zeroes in row 0 force columns 0 and 3 to become 0 as well.

Custom Notes
  • Brute force teaches why direct zeroing is dangerous.
  • Better approach is easiest to explain under pressure.
  • Optimal approach reuses first row and first column as markers.
  • Collision point is matrix[0][0], so keep a separate col0 flag for the first column.
  • Memory hook: mark, scan, then zero from the markers.
Brute Force Approach : TC: SC:
1 / 3

Algorithm: Use a temporary marker value like -1 for cells that should later become 0.

Pseudo:

  • Traverse every cell in the matrix.
  • When matrix[i][j] == 0, mark all non-zero cells in row i as -1.
  • Mark all non-zero cells in column j as -1.
  • After the traversal, replace every -1 with 0.

Time: O(m*n*(m+n))

Space: O(1)

Why mention it: It clearly shows why changing directly to 0 during the first pass creates accidental extra zeroes.

Better Approach : TC: SC:
2 / 3

Algorithm: Store which rows and columns must become 0 in two helper arrays.

Pseudo:

  • Create row[m] and col[n] initialized with 0.
  • First pass: if matrix[i][j] == 0, set row[i] = 1 and col[j] = 1.
  • Second pass: if row[i] == 1 or col[j] == 1, set matrix[i][j] = 0.

Time: O(m*n)

Space: O(m+n)

Interview line: This is the cleanest version when the interviewer does not insist on constant extra space.

Optimal Approach : TC: SC:
3 / 3

Algorithm: Use the first row and first column of the matrix itself as marker storage.

Pseudo:

  • Keep a variable col0 = 1 to remember whether column 0 must become 0.
  • First pass: when matrix[i][j] == 0, mark matrix[i][0] = 0 and matrix[0][j] = 0.
  • If j == 0, set col0 = 0 because the first column also needs zeroing.
  • Second pass: iterate from bottom-right and zero matrix[i][j] when matrix[i][0] == 0 or matrix[0][j] == 0.
  • At the end of each row, if col0 == 0 then set matrix[i][0] = 0.

Time: O(m*n)

Space: O(1)

Key insight: row 0 and col 0 become free marker arrays, while col0 solves the matrix[0][0] collision.

PCode
1 / 3
FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            mark all non-zero cells in row i as -1
            mark all non-zero cells in column j as -1

FOR each row i
    FOR each column j
        IF matrix[i][j] == -1
            matrix[i][j] = 0

RETURN matrix
PCode
2 / 3
rows = number of rows
cols = number of columns
row[0...rows-1] = 0
col[0...cols-1] = 0

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            row[i] = 1
            col[j] = 1

FOR each row i
    FOR each column j
        IF row[i] == 1 OR col[j] == 1
            matrix[i][j] = 0

RETURN matrix
2 / 2
01B/191
Set Matrix Zero
Continue
PCode
3 / 3
rows = number of rows
cols = number of columns
col0 = 1

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            matrix[i][0] = 0
            IF j != 0
                matrix[0][j] = 0
            ELSE
                col0 = 0

FOR i from rows - 1 down to 0
    FOR j from cols - 1 down to 1
        IF matrix[i][0] == 0 OR matrix[0][j] == 0
            matrix[i][j] = 0
    IF col0 == 0
        matrix[i][0] = 0

RETURN matrix