cc150-1.7

gistfile1.java

package ch1;


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

* First, we at least need two loops, one for finding out the rows and columns containing 0,
* the other one to set 0. We cannot do it in one loop, because it will influence result.
* We set the row and column which contain 0, true.
* Then in the next loop, if row or column is true, we set it 0.
* 
* Note: "or" is very important here, think about it. I used three loops initially, which is not most efficient. 

 Time Complexity O(MN) Space O(M+N)
 
*/

public class SetMatrix0 {
	
	public static void set0(int[][] matrix) {
		boolean[] rowMark = new boolean[matrix.length];
		boolean[] columnMark = new boolean[matrix[0].length];
		
		for(int i=0; i<matrix.length; i++) {
			for(int j=0; j<matrix[0].length; j++){
				if(matrix[i][j] == 0) {
					rowMark[i] = true;
					columnMark[j] = true;
				}
			}
		}
		
		for (int i=0; i<rowMark.length; i++){
			for (int j=0; j<columnMark.length; j++){
				if(rowMark[i] || columnMark[j]) {
						matrix[i][j]=0;
				}
			}
		}
		}
	

	public static void main(String[] args) {

		int[][] test = {{11, 2 ,3 ,4}, {0, 6, 1,2}, {1, 13, 4, 6}};
		set0(test);
		
		for(int i=0; i<test.length; i++) {
			for(int j=0; j<test[0].length; j++){
				System.out.print(test[i][j] + " ");
			}
			System.out.println(" ");
		}

	}

}