Tag Archives: matrix

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

Rotate an n-by-n matrix 90 degrees clockwise in place — A conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

====================================================================

Rotate an n-by-n matrix 90 degrees clockwise in place.
Q: What is the unknown? What is our goal?
A: A way to rotate a matrix in place.
Q: What are the conditions?
A: The matrix is n-by-n. We rotate 90 degrees clockwise. And we have to do it in place.
Q: What does it mean by “in place”?
A: That means you have to do this on the matrix itself with no support from other data structures.
Q: What are the data?
A: An n-by-n matrix.
Q: Can you give me some examples?
A: Sure. Say a 3-by-3 matrix is
                                               [1,2,3]
                                               [4,5,6]
                                               [7,8,9]
     And a 4-by-4 matrix is
                                               [1,2,3,4]
                                               [5,6,7,8]
                                               [9,10,11,12]
                                               [13,14,15,16]
Q: Have you seen it before? Or have you seen a similar problem in a slightly different form?
A: Not really, although I did work on something else on matrix.
Q: And what is that?
A: Ah simply switch the elements of a matrix across a diagonal.
Q: Do you think you can use it including its result and method?
A: I don’t know…
Q: OK, let’s look at your example here. Suppose you rotate the 3-by-3 matrix. What will you get in the end?
A: Well I will get the following matrix:
                                               [7,4,1]
                                               [8,5,2]
                                               [9,6,3]
Q: What if you switch elements across the diagonal? What will you get?
A: I will get:
                                               [1,4,7]
                                               [2,5,8]
                                               [3,6,9]
Q: So how far is this matrix to the expected matrix?
A: Let me see. Oh I get it! It is a mirror switch!
Q: Correct. What steps did we do to rotate the matrix?
A: switch the elements across the diagonal and then mirror switch the elements across the middle column of the matrix.
Q: Good. But is it also true for a 4-by-4 matrix? 
A: Let me test it….Yeah it is also true.
Q: Nice. Now you have a plan. Implement it carefully.
(Note: The solution on the book use a different approach which I think is a bit complicated to implement. The running time is O(n^2) too. But it does provide
a different perspective: rotate the matrix layer by layer–start with the outer layer then move into the next one…)
If you do not know a similar problem (like the switch elements across the diagonal), ask yourself what kind of switching operation can you do on a matrix? (Similar to the question: What operation can you do with bits?)
That may help you list a few operations which include the diagonal and mirror switch. Try those switch and compare the result with the expected result.
If you cannot do it in one step, try to do it in several steps.
Link to the Java Code on GitHub:
Enhanced by Zemanta