I'd like to keep posting programming problems regularly. I enjoy them very much, and I think they're a very good excercise to anyone trying to become a better programmer.
I'll try to post one challenge every week starting today (every Sunday.) Hopefully I'll have time to find a problem and code my own solution for it.
Write a function to rotate an NxN matrix by 90 degrees. You should rotate it in place, meaning you can't use another matrix to perform the rotation, but instead you have to use the same given structure.
What makes this problem a little bit complicated is that we can't use a separate matrix to do the rotation. That would have been simpler.
Before anything, I tried to come up with a formula that computed the new position in the matrix a specific value should go after rotated. Something that given [0, 0] in a 4x4 matrix, returns [0, 3]. Or [1, 1] when [1, 2] was provided.
I couldn't in a reasonable amount of time, so I moved on.
(But I'm sure somebody will, so please let me know.) (Florian sent me a formula that works:
(newRow, newCol) = (N - currentRow - 1, currentCol). Can you use it to make the algorithm below more efficient/elegant?)
From there, I started working in a different algorithm. Here are some notes I took when thinking about the problem. Hopefully they make sense:
To rotate a matrix by 90 degrees, we can consecutively rotate all the different rings of the matrix (starting from the outermost ring and working our way to the innermost one.) For the following 4x4 example:
1 2 3 4
5 6 7 8
9 a b c
d e f g
The first ring will be 1, 2, 3, 4, 8, c, g, f, e, d, 9, 5. The second ring will be 2, 3, 7, b, a, 6. For each ring, we can rotate the edges, gradually moving to the inside.
I tried hard to provide the best solution I could in the time I had, but I might very well be wrong (or you might have a better way of solving the problem.) If that's the case, please let me know and I'll update the post.
In case you are interested, here is the next challenge in the list: Programming challenge: merging overlapping intervals.