Set Matrix Zeroes - Java Solution

1. Introduction

This blog post explores a common matrix manipulation problem known as "Set Matrix Zeroes". The challenge is to modify a given matrix by setting entire rows and columns to zeroes if an element in the matrix is zero. This problem is a test of efficient matrix traversal and in-place modification.

Problem

Given an m x n integer matrix, the task is to set its entire row and column to 0's if an element is 0. This must be done in-place, which means modifying the input matrix directly without using additional data structures for storage.

2. Solution Steps

1. First pass: Iterate through the matrix to identify the rows and columns that need to be set to zero.

2. Use the first row and first column of the matrix as markers to store which rows and columns need to be zeroed.

3. Special handling for the first row and first column to determine if they themselves need to be zeroed.

4. Second pass: Use the markers to set the appropriate rows and columns to zero.

5. Update the first row and first column as per the markers.

3. Code Program

public class SetMatrixZeroes {
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 1, 1},
            {1, 0, 1},
            {1, 1, 1}
        };
        setZeroes(matrix);
        printMatrix(matrix); // Test the function and print the modified matrix
    }

    // Function to set matrix rows and columns to zero if an element is zero
    public static void setZeroes(int[][] matrix) {
        boolean firstRowZero = false, firstColZero = false;
        int m = matrix.length, n = matrix[0].length;

        // Check if the first row or first column needs to be set to zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = true;
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }

        // Use first row and column as markers
        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;
                }
            }
        }

        // Set matrix elements to zero based on 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;
                }
            }
        }

        // Set first row and column to zero if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    // Helper function to print the matrix
    private static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            for (int val : row) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }
}

Output:

0 0 0
0 0 0
0 0 0

Explanation:

1. setZeroes: This function sets entire rows and columns to zero in a matrix based on the presence of zero elements.

2. It first determines if the first row or first column should be zeroed.

3. The first row and column are then used as markers to record which rows and columns need to be zeroed.

4. The function iterates through the rest of the matrix, setting the elements to zero based on these markers.

5. Finally, it updates the first row and column based on the initial check.

6. printMatrix: A helper function to print the matrix, showing the results of the modification.

7. The in-place modification results in a matrix where any row or column containing a zero element is entirely set to zero.