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
Advertisements

One thought on “Rotate an n-by-n matrix 90 degrees clockwise in place — A conversation

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