73. Set Matrix Zeroes

#matrix #array

Intuition

We need to set entire rows and columns to 0 if any element is 0, without using extra space. The challenge is to avoid overwriting original 0s too early, which would cause incorrect updates.

To solve this smartly, we can use the first row and first column of the matrix itself as flags to remember which rows and columns should be zeroed. But since the first row and column are used as markers, we separately track if they themselves should be zeroed.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(nm)$

Code

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;

    boolean firstRowIsZero = false, firstColumnIsZero = false;

    // Step 1: Check if first row or first column contains any 0
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstColumnIsZero = true;
    }
    for (int i = 0; i < n; i++) {
        if (matrix[0][i] == 0) firstRowIsZero = true;
    }

    // Step 2: Use first row and column as markers for rows and columns to zero
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0; // mark row
                matrix[0][j] = 0; // mark column
            }
        }
    }

    // Step 3: Set matrix cells to 0 based on the markers
    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;
            }
        }
    }

    // Step 4: Handle first column
    if (firstColumnIsZero) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }

    // Step 5: Handle first row
    if (firstRowIsZero) {
        for (int i = 0; i < n; i++) {
            matrix[0][i] = 0;
        }
    }
}