/*Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0. */ /*Using bit vector*/ public class Program { static void SetZeroes(int [][] matrix) { boolean RowHasZeroes = false; boolean ColHasZeroes = false; for(int j = 0;j < matrix[0].length;j++) { if(matrix[0][j] == 0) { RowHasZeroes = true; break; } } for(int i = 0;i < matrix.length;i++) { if(matrix[i][0] == 0) { ColHasZeroes = true; break; } } for(int i = 1;i < matrix.length;i++) { for(int j = 1;j < matrix[i].length;j++) { if(matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for(int i = 1;i < matrix.length;i++) { if(matrix[i][0] == 0) { NullifyRows(matrix,i); } } for(int j = 1;j < matrix[0].length;j++) { if(matrix[0][j] == 0) { NullifyCols(matrix,j); } } if(RowHasZeroes) { NullifyRows(matrix,0); } if(ColHasZeroes) { NullifyCols(matrix,0); } } static void NullifyRows(int matrix[][],int Row) { for(int j = 0;j < matrix[0].length;j++) { matrix[Row][j] = 0; } } static void NullifyCols(int matrix[][],int Cols) { for(int i = 0;i < matrix.length;i++) { matrix[i][Cols] = 0; } } static void PrintMatrix(int [][] matrix) { for(int i = 0;i < matrix.length;i++) { for(int j = 0;j < matrix[0].length;j++) { System.out.print(" "+matrix[i][j]); } System.out.println(); } } public static void main(String[] args) { int arr [][] = {{1,2,3},{4,0,6},{7,8,9}}; System.out.println("The given matrix is : "); PrintMatrix(arr); SetZeroes(arr); System.out.println("\nThe zeroed matrix is : "); PrintMatrix(arr); } }

ZeroMatrix(solution 3)