[CC150][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.

Solution.java

//* Time O(MN)
//  Use two extra boolean arrays to record which rows and cols should be set to 0.
//* Space O(M+N)

public class Solution{
	private int[][] matrix;
	private int M;
	private int N;
	
	public Solution(int[][] m) {
		if (m == null) throw new NullPointerException();
		this.matrix = m;
		this.M = m.length; 	    // row
		this.N = m[0].length;	// col
	}
	public void setZero () {
		boolean[] rowFlag = new boolean[M];
		boolean[] colFlag = new boolean[N];
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++)
				if (matrix[i][j] == 0 ) {
					rowFlag[i] = true;
					colFlag[j] = true;
				}
		}
		
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++)
				if (rowFlag[i] || colFlag[j])
					matrix[i][j] = 0;
		}
	}
	
	public String toString() {
		String s = "";
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++)
				s += matrix[i][j] + " ";
			s += "\n";
		}
		return s;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("***********TEST**************");
		int[][] testA = {{1}};
		Solution a = new Solution(testA);
		System.out.print(a.toString());
		
		a.setZero();
		System.out.print(a.toString());;
		
		System.out.println("***********TEST**************");
		int[][] testB = {{1,0},{3,4}};
		Solution b = new Solution(testB);
		System.out.print(b.toString());
		
		b.setZero();
		System.out.print(b.toString());;
		
		System.out.println("***********TEST**************");
		int[][] testC = {{1,2,3},{4,0,6},{7,8,9}};
		Solution c = new Solution(testC);
		System.out.print(c.toString());
		
		c.setZero();
		System.out.print(c.toString());;
		
	}

}