Set Matrix Zeros (Java and Python)

Set Matrix Zeroes

 Total Accepted: 10610 Total Submissions: 35135My Submissions

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

	# without extra space
	class Solution:
	# @param matrix, a list of lists of integers
	# RETURN NOTHING, MODIFY matrix IN PLACE.
	def setZeroes(self, matrix):
	if matrix==None or len(matrix)==0:
	return
	# use first col and row as buffer to hold a flag to check if accordinate col or row should be 0
	# before do that, declare two flag used to check if first col and row need be change to 0 at the end
	first_row_to_zero=False
	first_col_to_zero=False
	# check the if first row and first col need to be changed to 0 at end
	if matrix[0][0]==0:
	first_row_to_zero=True
	first_col_to_zero=True
	else:
	if 0 in matrix[0]:
	first_row_to_zero=True
	if len([matrix[x][0] for x in range(0, len(matrix)) if matrix[x][0]==0])>0:
	first_col_to_zero=True
	# if find a cell with 0 then set accordinate first row and col to set as a flag
	for i in range(1, len(matrix)):
	for j in range(1, len(matrix[0])):
	if matrix[i][j]==0:
	matrix[0][j]=0
	matrix[i][0]=0
	# base on the all the flag in first row and col set 0 to the cell
	for i in range (1, len(matrix)):
	for j in range(1, len(matrix[0])):
	if matrix[0][j]==0 or matrix[i][0]==0:
	matrix[i][j]=0
	# use pre-marked flag to decide if first row and col need to be changed to 0
	if first_row_to_zero:
	for i in range(0, len(matrix[0])):
	matrix[0][i]=0
	if first_col_to_zero:
	for i in range (0, len(matrix)):
	matrix[i][0]=0
	# with O(rows+cols) extra space
	class Solution:
	# @param matrix, a list of lists of integers
	# RETURN NOTHING, MODIFY matrix IN PLACE.
	def setZeroes(self, matrix):
	if matrix==None or len(matrix)==0:
	return
	cols=[False]*len(matrix[0])
	rows=[False]*len(matrix)
	for col in range(len(matrix[0])):
	for row in range(len(matrix)):
	if matrix[row][col]==0:
	cols[col]=True
	rows[row]=True
	for col in range(len(matrix[0])):
	for row in range(len(matrix)):
	if cols[col] or rows[row]:
	matrix[row][col]=0

view raw SetMatrixZeroes.py hosted with ❤ by GitHub

	public class Solution {
	public void setZeroes(int[][] matrix) {
	if (matrix==null||matrix.length==0){
	return;
	}
	boolean[] rows=new boolean[matrix.length];
	boolean[] cols=new boolean[matrix[0].length];
	for (int row=0; row<matrix.length; row++){
	for (int col=0; col<matrix[0].length; col++){
	if (matrix[row][col]==0){
	rows[row]=true;
	cols[col]=true;
	}
	}
	}
	for (int i=0; i<matrix.length; i++){
	for (int j=0; j<matrix[0].length; j++){
	if (rows[i]||cols[j]){
	matrix[i][j]=0;
	}
	}
	}
	}
	}

view raw SetMatrixZeros.java hosted with ❤ by GitHub