Algorithm to set the entire row and column to zero if an element in an MXN matrix is zero.

Its a pretty tricky one. However if you start it out without doing a rough paper sketch you will definitely end up making all elements of your matrix as 0.

Following is a solution along with the proper reasoning of the solution.


public class MatrixRowSetToZero {

/**
* @param args
*/
public static void main(String[] args) {
int[][] matrix = new int[4][];
for (int i = 0; i < matrix.length; i++) {
matrix[i] = new int[7];
for (int j = 0; j < matrix[i].length; j++) {
matrix[i][j] = (i + j * 3);

}
}
matrix[2][5] = matrix[2][5] = matrix[2][6] = 0;
for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
System.out.println("-----------------------");
setZeros(matrix);
for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}

/**
* Wrong approach -> Traversing from top left to bottom right -1 =>along the
* diagonal one can say. If any element in the r1,c1 is found 0 1. Make all
* elements in that row and column to 0 2. skip to next row and next column
* element
*
* This will make the entire matrix as 0's so it is not a solution as every
* row and column will be made to 0.
*/
/**
* We do two pass of the entire matrix.
*
* 1. So, we keep two arrays one for rows and one for columns. Every time we
* encounter an element 0 we record the row and column if they are not
* already present in the arrays.
*
* 2. We than do the second pass of the array and then make every element 0,
* whose row or column lie within the arrays
*/
public static void setZeros(int[][] matrix) {
int[] rowArray = new int[matrix.length];
int[] colArray = new int[matrix[0].length];
/**
* first pass -> set 1 in the column index and row index within the rowArray and colArray respectively,  where the element 0 is encountered.
*/
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
rowArray[i] = 1; // ==> row i has an element with 0 value
// and should be set to 0 entirely
colArray[j] = 1; // ==> column j has an element with 0 value
// and should be set to 0 entirely
}
}
}

/**
* second pass -> set the element to 0 if in case its row index or its column index is found as 1 in the row or column array respectively.
*/
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (rowArray[i] == 1 || colArray[j] == 1) {
matrix[i][j] = 0;
}
}
}

}

}