This post is a bit more technical than usual, but don’t worry, there are pictures.
I was having a lovely time working through the Arrays and Strings section of Cracking the Coding Interview until I reached this problem:
Rotate Matrix: Given an image represented by an NxN matrix** … write a method to rotate the image by 90 degrees. Can you do this in place?
This is a deceptively tricky problem, and I had to draw quite a few diagrams in order to understand it. Let’s walk through it.
First, for our purposes, a matrix is a two-dimensional array. While the problem suggests that we should be able to apply this solution to a very large matrix (like an image), I have found that a 4×4 array is the easiest way to visualize this problem. Here is the basic example that I will be referencing throughout the post:
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
Our function to rotate it by 90 degrees should return:
[13, 9, 5, 1],
[14, 10, 6, 2],
[15, 11, 7, 3],
[16, 12, 8, 4]
The Approach: We will tackle this matrix layer by layer, starting from the outermost layer and working inwards. Since the problem is to rotate the matrix “in place” instead of making a copy of the matrix, we will swap each element individually, moving it from its current position to the position 90 degrees from it.
This requires that, for any element, we can find the coordinates of its position when rotated 90 degrees. We can then loop through each element and rotate it by swapping it with the element that is a 90 degree rotation from it.
It took a while to come up with a methodical system to find these coordinates, but with a little help from my friends and the internet, here’s what I’ve got:
The Coordinates: In order to find each set of coordinates, we need three variables:
- The width of the matrix, N.
- The Layer of the matrix that we are inspecting, starting with 0 (the outermost layer)
- The Position of the element that we are inspecting within its row. This can also be thought of as the element’s offset from the end of the row.
Using these three variables, We can establish that for any layer and position, the four corresponding elements that need to be swapped are:
To help visualize this, I have created a diagram of these coordinates on our 4×4 matrix
You can view and test my final solution to the problem here.