Rotate the Image!
I grappled with a Leetcode problem a while ago where I was asked to rotate an image. The image was actually a 2D matrix, which is essentially an array of arrays. The image needed to be rotated 90 degrees clockwise and it had to be done IN PLACE…in other words, I could not create a new matrix as part of the solution.
I have to admit, it took me a while to think about this. Before writing any code, I had to visualize what was going on and what needed to be done. So I did some sketching.
The above image shows an array of 6 sub-arrays, with each row representing its own sub-array. Notice the corners have been highlighted. What essentially has to happen is that each of those numbers has to be swapped with the number in the corner to the right (moving clockwise). And then each number following the corner in each sub-array has to be swapped with the number following the corner to the right.
Well, that sounds super confusing, doesn’t it?
Let’s take it slowly, starting with the corners.
In order to keep track of what is being swapped, let’s create an anchor position, which will start at the top left corner.
Our first step will be to swap the number 1, which is in our anchor position, with 6. Then we will swap 36 with what is in our anchor position, which at this point would be the 6 (that was the result of the previous swap). Finally, we will swap 31 with what is in our anchor position, which would be 36. So we can think of our anchor position almost like a revolving door, something goes in and then comes right back out. This happens THREE TIMES.
Great…but we’re nowhere near done! The question didn’t ask us to just swap the corners, after all. This means that our anchor position needs to move! So we advance that anchor position by one…and do another three swaps.
And we keep doing that until we reach the end of that first row, which means no more anchor positions in that row. The result looks like this, with the last swap not being complete (the 32 has to be swapped with the 7 to finish it off).
Notice that what we’ve done is completed a “ring”…the top row and bottom row, along with the first column and last column have been successfully rotated! Once you see this pattern, completing the rest of the matrix gets much easier…we just have to keep working in “rings.” Essentially, we keep moving towards the center by moving down rows from the top, up rows from the bottom, and one column in on both the right and left sides.
Our anchor position now has to move down one and in one.
We can now look at this “inner ring”, with the upper left anchor position at the second row/second column position. And we do the same swapping process we did with the “outer ring.” In the image above, I show the first three groups of three swaps…with red lines showing the first three swaps, green lines showing the second three swaps, and blue lines showing the third three swaps.
Once we finish all of those swaps, we once again want to move into a deeper inner ring…in the case of this example, it’s the final inner ring. Our anchor position is now at the third row/third column. And we only have to do one round of three swaps.
Once we finish those final three swaps, we are left with our totally rotated image!
Whew! Now we actually have to write the code!
We’re going to write a helper function, swap(), in order to do the actual swapping…this is going to be a typical swap function, keeping mind that we will have to use two indices to indicate positions since we have a 2D matrix.
We will use that helper function as we iterate through our matrix.
Below is the code with annotations to explain the process.
And that’s it!