Set Matrix Zeroes

MediumMath & GeometryBlind 75MidOpen on LeetCodeUpdated Nov 11, 2026

You're given an m x n integer matrix. Wherever an element is 0, set its entire row and its entire column to 0. Modify the matrix in place. A straightforward solution uses O(m + n) extra space; as a follow-up, use only O(1).

Examples

matrix = [[4,0,2],[3,5,1]] returns [[0,0,0],[3,0,1]]

input

output

The 0 in row 0, column 1 clears all of row 0 and all of column 1.

matrix = [[1,2,3],[4,5,0],[7,8,9]] returns [[1,2,0],[0,0,0],[7,8,0]]

The 0 in the middle row's last column clears that row and that column.

matrix = [[0,1],[1,1]] returns [[0,0],[0,1]]

A zero in the corner clears the first row and the first column. Zeros written during the update must not trigger more clearing.

Constraints

1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

Hints

Hint 1

You can't clear as you go, because new zeros would look like original ones. What do you need to remember before you start clearing?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Use the first row and first column as the marker arrays. Scan the matrix: when matrix[r][c] is 0, set matrix[r][0] and matrix[0][c] to 0. Cell matrix[0][0] can only mark row 0, so track whether column 0 needs clearing with a separate flag. Then walk the matrix from the bottom-right corner back to the top, clearing matrix[r][c] for c >= 1 when its row or column marker is 0, and clearing column 0 last in each row if the flag is set. Going backwards means the markers in row 0 are read before row 0 itself is overwritten. O(m * n) time, O(1) extra space.

Time

O(m * n)

Space

O(1)

Pitfall

Zeroing rows and columns during the first scan. The new zeros look like original ones, and the clearing spreads until the whole matrix is 0. Record first, then clear.

Solutions

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstColZero = false;
        for (int r = 0; r < m; r++) {
            if (matrix[r][0] == 0) firstColZero = true;
            for (int c = 1; c < n; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }
        for (int r = m - 1; r >= 0; r--) {
            for (int c = n - 1; c >= 1; c--) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
            }
            if (firstColZero) matrix[r][0] = 0;
        }
    }
}

class Solution:
    def setZeroes(self, matrix) -> None:
        m, n = len(matrix), len(matrix[0])
        first_col_zero = False
        for r in range(m):
            if matrix[r][0] == 0:
                first_col_zero = True
            for c in range(1, n):
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0
        for r in range(m - 1, -1, -1):
            for c in range(n - 1, 0, -1):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0
            if first_col_zero:
                matrix[r][0] = 0