73. Set Matrix Zeroes

Problem Statement

Pattern:

---

Solution

public void setZeroes(int[][] matrix) {
	// flag if initial zero occurs in first row or column
	boolean fr = false, fc = false;
	int m = matrix.length, n = matrix[0].length;
 
	// set zero markers and flags
	for (int i = 0; i < m ; i++)
		for (int j = 0; j < n; j++)
			// mark first row and col of el as 0
			if(matrix[i][j] == 0) {
				// flag if el in fr or fc
				if (i == 0) fr = true;
				if (j == 0) fc = true;
				matrix[0][j] = 0;
				matrix[i][0] = 0;
			}
 
	// use markers to set rows and columns to zero
	for (int i = 1; i < m; i++)
		for (int j = 1; j < n; j++)
			if(matrix[0][j] == 0 || matrix[i][0] == 0)
				matrix[i][j] = 0;
 
	// if fr set first row to zero
	int index = 0;
	while(fr && index < n)
		matrix[0][index++] = 0;
 
	// if fc set first column to zero
	index = 0;
	while(fc && index < m) matrix[index++][0] = 0;
}

Notes

• Use the 0th row and column as markers. ie.
  • if any elment in the array is zero, set its currsponding 0’th row el and 0th column element as zero
  • Reiterate, set any element to zero if its 0th row or 0th cell is zero
• What if the 0th element is in the first row or column itself?
  • that why we have fc and fr flags
  • if any of those are found to be true, the first row and column itself if set to zero by the last while loops

- another point