Set Matrix Zeroes

Problem

Write a function to modify an m x n integer matrix matrix directly, such that if any element in the matrix is 0, its entire corresponding row and column are set to 0. This transformation should be done in place, without using any additional data structures for storage.

Input:

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

Output:

[
    [0,0,0],
    [0,5,6],
    [0,8,9]
]

Explanation: Since the element at the first row and first column is 0, set all elements in the first row and first column to 0.

Understanding the Problem

The naive approach would use O(m + n) extra space by storing which rows and columns need to be zeroed in separate sets. But we can do better by using the matrix itself as storage.

Use the Matrix Itself!

Instead of extra arrays, we can use the first row and first column as markers. When we find a zero at [i][j], we mark:

matrix[i][0] = 0 → “row i needs to be zeroed”
matrix[0][j] = 0 → “column j needs to be zeroed”

But there’s a catch! If we modify the first row/column while scanning, we’ll lose information about whether they originally had zeros. So we save that first.

Walkthrough

Let’s trace through matrix = [[1,1,1],[1,0,1],[1,1,1]]:

Step 1: Save first row/column state

Check if the first row or column originally contains any zeros. Save in boolean flags.

Step 2: Mark zeros using first row/column

Scan the inner matrix [1:][1:]. When we find a zero, mark the corresponding first row and first column cells.

Step 3: Zero the inner matrix

Use the markers to zero out cells. If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.

Step 4: Handle first row/column

If our saved flags indicate the first row/column originally had zeros, zero them now.

The order is crucial: we must save the first row/column state before using them as markers, and zero them last so we don’t corrupt the markers we’re reading.

Solution

def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_zero = any(matrix[i][0] == 0 for i in range(rows))

    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if first_row_zero:
        for j in range(cols):
            matrix[0][j] = 0

    if first_col_zero:
        for i in range(rows):
            matrix[i][0] = 0

public void setZeroes(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    boolean firstRowZero = false;
    boolean firstColZero = false;

    for (int j = 0; j < cols; j++) {
        if (matrix[0][j] == 0) firstRowZero = true;
    }
    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) firstColZero = true;
    }

    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    if (firstRowZero) {
        for (int j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }

    if (firstColZero) {
        for (int i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
}

func setZeroes(matrix [][]int) {
    rows := len(matrix)
    cols := len(matrix[0])
    firstRowZero := false
    firstColZero := false

    for j := 0; j < cols; j++ {
        if matrix[0][j] == 0 {
            firstRowZero = true
        }
    }
    for i := 0; i < rows; i++ {
        if matrix[i][0] == 0 {
            firstColZero = true
        }
    }

    for i := 1; i < rows; i++ {
        for j := 1; j < cols; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    for i := 1; i < rows; i++ {
        for j := 1; j < cols; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }

    if firstRowZero {
        for j := 0; j < cols; j++ {
            matrix[0][j] = 0
        }
    }

    if firstColZero {
        for i := 0; i < rows; i++ {
            matrix[i][0] = 0
        }
    }
}

function setZeroes(matrix: number[][]): void {
    const rows: number = matrix.length;
    const cols: number = matrix[0].length;
    let firstRowZero: boolean = false;
    let firstColZero: boolean = false;

    for (let j = 0; j < cols; j++) {
        if (matrix[0][j] === 0) firstRowZero = true;
    }
    for (let i = 0; i < rows; i++) {
        if (matrix[i][0] === 0) firstColZero = true;
    }

    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
    }

    if (firstRowZero) {
        for (let j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }

    if (firstColZero) {
        for (let i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
}