Zero Matrix Best Time & Space Solution

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

To achieve the best time complexity of O(M*N) and space complexity of O(1), you can use the following algorithm:

1. Iterate through the matrix and for each cell, if the value is 0, mark the corresponding row and column indices as 0 in the first row and first column respectively.
2. Iterate through the first row and first column. For each cell, if the row index or column index is marked as 0, set the entire row or column in the matrix to 0.
3. Finally, if the first row was initially marked, set the entire first row to 0. If the first column was initially marked, set the entire first column to 0.

public class ZeroMatrix {
    public void setZeroes(int[][] matrix) {
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;
        
        // Mark the first row and first column if they contain zeros
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) firstRowHasZero = true;
                    if (j == 0) firstColHasZero = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        // Set zeros based on the marks in the first row and first column
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Set zeros for the first row and first column if marked
        if (firstRowHasZero) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        
        if (firstColHasZero) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
    
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 0, 6},
            {7, 8, 9}
        };
        
        ZeroMatrix zeroMatrix = new ZeroMatrix();
        zeroMatrix.setZeroes(matrix);
        
        // Print the modified matrix
        for (int[] row : matrix) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}