Set Matrix Zeroes

mediumAmazon-tagged: Arrays & Strings50 stepsJava · Python · C++

If a cell is 0, set its whole row and column to 0, using O(1) extra space. Use the first row and first column as marker storage: mark matrix[i][0] and matrix[0][j] for each zero, then fill. Two booleans remember whether the first row and column themselves need zeroing.

▶ Watch the animated trace

Traced input: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]] → [[1, 0, 1], [0, 0, 0], [1, 0, 1]]. Original problem: neetcode.io/problems/set-zeroes-in-matrix

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(1)

Two passes over the matrix.

Key idea

Zeroing immediately would spread zeros to cells that weren't originally zero.
The first row and column become flags for their columns and rows.
Record the first row/column's own status before overwriting them.
Zero the first row and column last.

Common mistakes

Zeroing cells during the scan cascades into wrong rows and columns.
Zeroing the first row/column too early destroys the markers.

Solution

Java

void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRow = false, firstCol = false;
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = true;
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
    if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}

Python

def setZeroes(matrix: List[List[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    first_row = any(matrix[0][j] == 0 for j in range(n))
    first_col = any(matrix[i][0] == 0 for i in range(m))
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0
    if first_row:
        for j in range(n): matrix[0][j] = 0
    if first_col:
        for i in range(m): matrix[i][0] = 0

C++

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRow = false, firstCol = false;
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = true;
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
    if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Zero in the first row The first row itself must be zeroed at the end.	`matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]`	`[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]`
No zeros Nothing changes.	`matrix = [[1, 2], [3, 4]]`	`[[1, 2], [3, 4]]`
Single cell zero Already zero.	`matrix = [[0]]`	`[[0]]`