[Leetcode] 73. Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/description/

initial

I thought of using set to store the rows and columns for 0s separately and iterate throguh set_row and set_col to modify matrix.

but the space is n+m cuz we are storing n rows and m cols.

public void setZeroesWithSets(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    Set<Integer> zeroRows = new HashSet<>();
    Set<Integer> zeroCols = new HashSet<>();

    // Find all zero rows and columns
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                zeroRows.add(i);
                zeroCols.add(j);
            }
        }
    }

    // Set zero rows
    for (int row : zeroRows) {
        for (int j = 0; j < n; j++) {
            matrix[row][j] = 0;
        }
    }

    // Set zero columns
    for (int col : zeroCols) {
        for (int i = 0; i < m; i++) {
            matrix[i][col] = 0;
        }
    }
}

to truely make it 1 space we cannot do this method

sol

we fist mark if there is any 0 in the first row or col with 2 boolean values. u will see why later.

core logic is that when we find a 0 from matrix[1][1] onwards, we mark the matrix[0][j] and matrix[i][0] as 0. So updating the leftmost and upmost grid as 0. This will be our marker so when we iterate through the first row, if that specific grid at that column is 0, we make that entire column 0. Same for iterating through the first col.

Then, as we iterate through matrix[1][1] onwards (excluding 0th row and 0th col), if we see that the marker is 0, then we make entire row or col as 0.

finally, we also need to consider 0th row and 0th col with the 2 boolean values and modify accordingly.

public void setZeroesOptimal(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    boolean firstRowZero = false;
    boolean firstColZero = false;

    // Check if first row has zero
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }

    // Check if first column has zero
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }

    // Use first row and column to mark zero rows and columns
    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;
            }
        }
    }

    // Zero rows based on marks
    for (int i = 1; i < m; i++) {
        if (matrix[i][0] == 0) {
            for (int j = 1; j < n; j++) {
                matrix[i][j] = 0;
            }
        }
    }

    // Zero columns based on marks
    for (int j = 1; j < n; j++) {
        if (matrix[0][j] == 0) {
            for (int i = 1; i < m; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    // Zero first row if needed
    if (firstRowZero) {
        for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }

    // Zero first column if needed
    if (firstColZero) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
}

compelxity

n*m time
1 space