Set Matrix Zeros

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?

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

Well, this is a rather easy question, without the last follow ups. I came up with O(m+n) space solution at the beginning and then struggled with the constant space solution.

The O(m+n) solution:

Get a boolean array of size m (called “rows”) and another of size n (called “cols”), then scan through the matrix. Say matrix[i][j] == 0, then we set rows[i] = true and cols[j] = true, which indicates that row i and column j should be set to zeros.

For the constant space solution, I had two thoughts. They failed, but I think it’s still worth writing down here:

  • Maybe we can do this change in place, with recursion (getting too complicated).
  • Bit operations. We use two integers rowCheck and colCheck, one for the rows and the other for the columns, initialized to 0. Think about their bit representation. rowCheck should have m bits while colCheck should have n bits. Say row 3 should be set to zeros, then the third bit in rowCheck should be set to 1. The program works fine for almost all test cases except for the last three. I haven’t figure out the reason yet. But it’s just good to know that bit operation is there for us to consider if constant space is required. 

So, I peek at the discussion forum and found a great solution:

  • For matrix cells that are neither on the first row nor on the first column, an zero in the cell matrix[i][j] means the same as having matrix[i][0] = 0 and matrix[0][j] = 0. So we can simply store the locations of zeros in the first row and first column.
  • But what about the cells on the first row and column? If we do the first step above, we are overriding the values and we won’t know if there are any zeros in the first row and column originally. Therefore, we have to check if there are zeros in them first.
  • Once the first two steps are done, we can use the info on the first row and column to set zeros in matrix[1:m][1:n]. Do not set cells on first row and column!
  • Final step, if there are zeros originally on the first row and column, set zeros in corresponding cells.

Code on github:

Enhanced by Zemanta
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