This problem comes from the truly awesome Cracking the Coding Interview:
“Given an image represented by an NxN matrix… write a method to rotate the [matrix] by 90 degrees. Can you do this in place?”
This one can get a bit brain-bendy, but if we take a step back and look at a simple case first, it might become more clear. If it's still muddy there's an animation and a link to a really great article that visualizes what's going on at the bottom.
So let's try to rotate the simplest useful matrix we can: a 2x2 matrix of integers. We'll represent the matrix as a 2-D array, and since there are only the four elements we can brute-force the rotation by swapping the appropriate corners.
This is the meat of each step we'll need to take to rotate a larger matrix.
The gist of the algorithm we'll need to solve the problem is to rotate the matrix from the outside-in, and from the corners first. If we break the matrix in to concentric "rings" that we rotate independently, it starts to follow that to rotate one layer, we just find the min and max indices, offset by the current step, and swap the corners until we hit the limit (i.e. that length of one side of the current layer).
I've tried to annotate the code below to try and make it clear what's happening at each step. Without a visual aid it's still kind of hard to follow...
BUT... Here's a handy visual for how the algorithm works! Check out the image credit for an even more in-depth visual break-down of the pinwheel algorithm.
