Problem statement

Given an m x n matrix, if an element is 0, set its entire row and column to 0, and return the matrix.

The follow-up asks for an in-place solution using O(1) extra space (use the first row and column as markers).

Example 1

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

Example 2

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

Constraints

• 1 <= m, n <= 7
• -50 <= matrix[i][j] <= 50

Hints for Set Matrix Zeroes

1. Hint 1

   First record WHICH rows and columns contain a zero, then wipe them.

2. Hint 2

   O(1) space: store the markers in row 0 and column 0 themselves.

How to solve Set Matrix Zeroes

The trap is doing it in one pass: zeroing a row immediately creates new zeros that the rest of the scan cannot distinguish from originals, and the wipe cascades over the whole matrix. Split it into two phases — first record which rows and columns contain an original zero, then apply the wipes.

Approach

1. Allocate a flag per row and per column, all false.
2. Scan the matrix; on each zero, mark that row and that column.
3. Scan again, setting a cell to zero when its row flag or its column flag is set.
4. Return the matrix.

Why it works

Separating detection from mutation is what keeps the operation faithful to the original matrix: the second pass reads only the flags, which were computed before anything changed, so a zero written in phase two can never trigger further wipes. The O(1)-space variant stores those same flags inside row 0 and column 0, which works but needs care because those cells serve double duty as both markers and data.

Complexity

• Time — O(rows · cols)
• Space — O(rows + cols), or O(1) using the first row and column as markers

Pitfalls

• Never wipe during the detection pass — the newly written zeros are indistinguishable from real ones and the whole matrix collapses.
• Flags are per row and per column; a single set of flags cannot capture both.
• In the O(1) variant, handle the first row and column separately at the very end, since they hold the markers.
• A cell is zeroed if either flag is set, not both.

Reference solution

Python

from typing import List

def setZeroes(matrix: List[List[int]]) -> List[List[int]]:
    rows = set()
    cols = set()
    for i, row in enumerate(matrix):
        for j, v in enumerate(row):
            if v == 0:
                rows.add(i)
                cols.add(j)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if i in rows or j in cols:
                matrix[i][j] = 0
    return matrix

Java

public static int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean[] zeroRow = new boolean[rows];
    boolean[] zeroCol = new boolean[cols];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 0) {
                zeroRow[i] = true;
                zeroCol[j] = true;
            }
        }
    }
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (zeroRow[i] || zeroCol[j]) matrix[i][j] = 0;
        }
    }
    return matrix;
}

C++

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = (int) matrix.size(), cols = (int) matrix[0].size();
    vector<bool> zeroRow(rows, false), zeroCol(cols, false);
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 0) {
                zeroRow[i] = true;
                zeroCol[j] = true;
            }
        }
    }
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (zeroRow[i] || zeroCol[j]) matrix[i][j] = 0;
        }
    }
    return matrix;
}

JavaScript

var setZeroes = function(matrix) {
    const rows = new Set(), cols = new Set();
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] === 0) { rows.add(i); cols.add(j); }
        }
    }
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (rows.has(i) || cols.has(j)) matrix[i][j] = 0;
        }
    }
    return matrix;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium