CC_1_7

MatrixZeros.java

// Cracking the Coding Interview
// 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.
import java.util.Arrays;
class MatrixZeros {
	public static void setZeros(int[][] m) {
		if (m.length <= 1 && m[0].length <= 1) return;
		boolean zeroAtFirstRow = false;
		boolean zeroAtFirstColumn = false;
		// check first row
		for(int j = 0; j < m[0].length; j++) {
			if (m[0][j] == 0) {
				zeroAtFirstRow = true;
				break;
			}
		}
		// check first column
		for(int i = 0; i < m.length; i++) {
			if (m[i][0] == 0) {
				zeroAtFirstColumn = true;
				break;
			}
		}
		// check whole matrix
		for(int i = 1; i < m.length; i++) {
			for(int j = 1; j < m[0].length; j++) {
				if (m[i][j] == 0) {
					m[i][0] = 0;
					m[0][j] = 0;
				}
			}
		}

		for(int j = 1; j < m[0].length; j++) {
			if (m[0][j] == 0) {
				// set column to be 0
				for(int i = 1; i < m.length; i++) {
					m[i][j] = 0;
				}
			}
		}
		if (zeroAtFirstRow) {
			for(int j = 0; j < m[0].length; j++) {
				m[0][j] = 0;
			}
		}

		for(int i = 1; i < m.length; i++) {
			if (m[i][0] == 0) {
				// set row to be 0
				for(int j = 1; j < m[i].length; j++) {
					m[i][j] = 0;
				}
			}
		}
		if (zeroAtFirstColumn) {
			for(int i = 0; i < m.length; i++) {
				m[i][0] = 0;
			}
		}		
	}

	public static void main(String[] args) {
		int[][] test1 = {{0}};
		int[][] result1 = {{0}};
		int[][] test2 = {{1}};
		int[][] result2 = {{1}};
		int[][] test3 = {{1}, {0}};
		int[][] result3 = {{0}, {0}};
		int[][] test4 = {{0, 1, 2}, {1, 4, 3}};
		int[][] result4 = {{0, 0, 0}, {0, 4, 3}};
		int[][] test5 = {{2, 1, 2}, {1, 0, 3}, {3, 7, 11}};
		int[][] result5 = {{2, 0, 2}, {0, 0, 0}, {3, 0, 11}};
		int[][] test6 = {{2, 3, 0}};
		int[][] result6 = {{0, 0, 0}};

		setZeros(test1);
		setZeros(test2);
		setZeros(test3);
		setZeros(test4);
		setZeros(test5);
		setZeros(test6);

		assert areEqual(test1, result1);
		assert areEqual(test2, result2);
		assert areEqual(test3, result3);
		assert areEqual(test4, result4);
		assert areEqual(test5, result5);
		assert areEqual(test6, result6);

		System.out.println("Test Passed\n");
	}

	private static boolean areEqual(int[][] arr1, int[][] arr2) {
		if (arr1 == arr2) return true;
		if (arr1 == null || arr2 == null || arr1.length != arr2.length) return false;
		for(int i = 0; i < arr1.length; i++) {
			if (!Arrays.equals(arr1[i], arr2[i])) return false;
		}
		return true;
	}

}