Set Matrix Zeroes @LeetCode

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?

	package leetcode;
	import java.util.ArrayList;
	/**
	* Solution: zero flags.(different spaces) O(mn).O(m+n)
	* Key problem is where we stores zero flags which determine the space.
	* O(m+n) --> reuse matrix space to store flags in first row and col.
	*
	* 1. Remember to start from 1 but not 0 in the middle part. or first row will affect result.
	* 2. Refactor setting entire row, col to 0. Old version are commented below.
	*
	* Reference:
	* http://fisherlei.blogspot.com/2013/01/leetcode-set-matrix-zeroes.html
	* http://blog.unieagle.net/2012/10/23/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Aset-matrix-zeroes/
	* @author jeffwan
	* @date Apr 2, 2014
	*/
	public class SetMatrixZeroes {
	public void setZeroes(int[][] matrix) {
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
	return;
	}
	int m = matrix.length;
	int n = matrix[0].length;
	boolean emptyFirstRow = false;
	boolean emptyFirstCol = false;
	// Check if there's 0 in first row.
	for (int i = 0; i < n; i++) {
	if (matrix[0][i] == 0) {
	emptyFirstRow = true;
	break;
	}
	}
	for (int i = 0; i < m; i++) {
	if (matrix[i][0] == 0) {
	emptyFirstCol = true;
	break;
	}
	}
	// Find 0 in matrix and place 1st row,col index 0
	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
	if (matrix[i][j] == 0) {
	matrix[i][0] = 0;
	matrix[0][j] = 0;
	}
	}
	}
	// Set entire row,col to 0
	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;
	}
	}
	}
	// set first row, col 0 according to emptyFirstRow, emptyFirstCol
	if (emptyFirstRow) {
	for (int i = 0; i < n; i++) {
	matrix[0][i] = 0;
	}
	}
	if (emptyFirstCol) {
	for (int i = 0; i < m; i++) {
	matrix[i][0] = 0;
	}
	}
	}
	/* set entire col to 0;
	for (int i = 1; i < n; i++) {
	if (matrix[0][i] == 0) {
	for (int j = 0; j < m; j++) {
	matrix[j][i] = 0;
	}
	}
	}
	// set entire row to 0;
	for (int i = 1; i < m; i++) {
	if (matrix[i][0] == 0) {
	for (int j = 0; j < n; j++) {
	matrix[i][j] = 0;
	}
	}
	}
	*/
	// My solution. Remember all rows and cols 0 is on. Time O(mn) but three pass.Space O(m+n).
	public void setZeroes2(int[][] matrix) {
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
	return;
	}
	int m = matrix.length;
	int n = matrix[0].length;
	ArrayList<Integer> rows = new ArrayList<Integer>();
	ArrayList<Integer> cols = new ArrayList<Integer>();
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (matrix[i][j] == 0) {
	rows.add(i);
	cols.add(j);
	}
	}
	}
	for (int row : rows) {
	for (int i = 0; i < n; i++) {
	matrix[row][i] = 0;
	}
	}
	for (int col : cols) {
	for (int i = 0; i < m; i++) {
	matrix[i][col] = 0;
	}
	}
	}
	}

view raw SetMatrixZeroes.java hosted with ❤ by GitHub