Set matrix’s row and col to zero

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

My initial thoughts:

  1. Scan the matrix, store the numbers of rows and columns that will be set to zero to two sets
  2. Iterate through those two sets and set corresponding row and col to zeros.

My initial codes:

	public static void setZero(int[][] matrix) {
		Set<Integer> rowToClear = new HashSet<Integer>();
		Set<Integer> colToClear = new HashSet<Integer>();
		for(int i = 0; i < matrix.length; ++i) {
			for(int j = 0; j < matrix[0].length; ++j) {
				if(matrix[i][j] == 0) {
					rowToClear.add(i);
					colToClear.add(j);
				}
			}
		}
		
		for(Integer row : rowToClear) {
			for(int j = 0; j < matrix[row].length; ++j) {
				matrix[row][j] = 0;
			}
		}
		
		for(Integer col : colToClear) {
			for(int i = 0; i < matrix.length; ++i) {
				matrix[i][col] = 0;
			}
		}
	}

Comments after running:

  1. It works fine.
  2. Time complexity O(M*N) and space complexity O(M+N).

Solutions:
The idea of the solution is similar to mine but it use two arrays to store the row and col numbers. Supposedly, this should use less memory than using java.util.Set. I improved the solution a little bit by utilizing boolean vectors:

		boolean[] rowBooleanVectors = new boolean[matrix.length];
		boolean[] colBooleanVectors = new boolean[matrix[0].length];
		for(int i = 0; i < matrix.length; ++i) {
			for(int j = 0; j < matrix[0].length; ++j) {
				if(matrix[i][j] == 0) {
					rowBooleanVectors[i] = true;
					colBooleanVectors[j] = true;
				}
			}
		}
		
		for(int i = 0; i < matrix.length; ++i) {
			for(int j = 0; j < matrix[0].length; ++j) {
				if( rowBooleanVectors[i] || colBooleanVectors[j])
					matrix[i][j] = 0;
			}
		}

If we assume the size of the matrix is not that big, we can, again, use bit-vector, which is constant memory complexity:

		int rowMask = 0, colMask = 0;
		for(int i = 0; i < matrix.length; ++i) {
			for(int j = 0; j < matrix[0].length; ++j) {
				if(matrix[i][j] == 0) {
					rowMask |= (1 << i);
					colMask |= (1 << j);
				}
			}
		}
		
		for(int i = 0; i < matrix.length; ++i) {
			for(int j = 0; j < matrix[0].length; ++j) {
				if( (rowMask & (1 << i)) != 0 ||
					 (colMask & (1 << j)) != 0 )
					matrix[i][j] = 0;
			}
		}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: