73. Set Matrix Zeroes

#matrix #array

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

A simple improvement uses O(m + n) space, but devise a constant space solution

---

Intuition

Approach

Complexity

Space Complexity	Time Complexity
$\text{O}(n+m)$	$\text{O}(nm)$

• We iterate over all the elements in the matrix

Code

public void setZeroes(int[][] matrix) {
	boolean [] rowIsZero = new boolean[matrix.length];
	boolean [] columnIsZero = new boolean[matrix[0].length];

	for (int i = 0; i < matrix.length; ++i) {
		for (int j = 0; j < matrix[i].length; ++j) {
			if(matrix[i][j] == 0 ){
				rowIsZero[i] = true;
				columnIsZero[j] = true;
			}
		}
	}


	for (int i = 0; i < matrix.length; ++i) {
		for (int j = 0; j < matrix[i].length; ++j) {
			if(rowIsZero[i] || columnIsZero[j]) {
				matrix[i][j] = 0;
			}
		}
	}

}