Rotating a Matrix (with Gifs!)

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]
]

Note: The first element of a JavaScript array has an index of 0, the last element has an index of array.length -1. Each element of the matrix can be referenced by its position in the outer array followed by its position in the inner array, so matrix[0][2] = 3.

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. 

flipmatrix

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:

  1. The width of the matrix, N.
  2. The Layer of the matrix that we are inspecting, starting with 0 (the outermost layer)
  3. 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:

matrix[Layer][Pos]
matrix[Pos][N-Layer-1]
matrix[N-Layer-1][N-Pos-1]
matrix[N-Pos-1][Layer]

To help visualize this, I have created a diagram of these coordinates on our 4×4 matrix

screen-shot-2016-11-18-at-10-15-48-amscreen-shot-2016-11-18-at-10-16-15-amscreen-shot-2016-11-18-at-10-16-27-amscreen-shot-2016-11-18-at-10-16-37-am

You can view and test my final solution to the problem here.

** I have eliminated the portion of the question concerned with memory, since I am working in JavaScript and memory is magically taken care of.

Advertisements

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