Daily Coding Problem: Rotating Matrices

Welcome back with another problem to solve! Today, we’ll be talking about matrices and how to rotate them. We’ll see two ways of doing this: one will take extra space to accomplish the task, and the other one will do it in place!

As always, these problems are provided by the wonderful newsletter Daily Coding Problem, which you can subscribe to here! Check it out and try to solve your daily challenge!

Without further ado, let’s take a look at the problem, which (may) have been asked by Facebook in one of their job interviews.

Given an N by N matrix, rotate it by 90 degrees clockwise.

For example, given the following matrix:

[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

you should return:

[[7, 4, 1],
[8, 5, 2],
[9, 6, 3]]

Follow-up: What if you couldn’t use any extra space?

Let’s give this a try by hand with a smaller matrix and see which transformation we can apply to get the result.

Matrices and transformations

First off, let’s start to manually rotate a smaller matrix, for example, the matrix [ [1,2],[3,4] ] .

There are basically two ways to visualize it: you can literally rotate the actual image of the matrix, adjusting the final position of its elements at the end, or you can imagine swapping each element to its right neighbor, following the “border” of the matrix.

The first thing we can notice is the position of the elements after the rotation: basically, the first row has become the last column, and the second row has become the first column. We’ll discuss more about this later, but for now, we can use this approach to build our first algorithm: we’ll simply swap the rows for the columns and place them accordingly in a new matrix.

The code (not in place)

Let’s see how we can make the code work: we’ll use Go this time!

https://gist.github.com/NicolaM94/a5a04dc9a5de808565148ea7701c5b17?embedable=true#file-main-go

First off, we create a function that takes a parameter in the matrix we want to rotate and returns a new matrix out, the rotated version. Right after that, we initialize the new matrix, which will be the same size as the initial matrix, just full of zeros. After that, for each row of the starting matrix, we append the elements in the right place in each column.

To better explain the concept, let’s walk it row by row in the example above, where the starting array is [][]int{{1,2},{3,4}} :

• row = 0 -> col = 0 -> out[0][2-1-0] = matrix[0][0]
• row = 0 -> col = 1 -> out[1][2-1-0] = matrix[0][1]
• row = 1 -> col = 0 -> out[0][2-1-1] = matrix[1][0]
• row = 1 -> col = 1 -> out[1][2-1-1] = matrix[1][1]

One important thing to point out about this: we can use this approach because the problem explicitly states that the matrices we are working with are NxN, and so are square matrices. If they were not square, we would need to adapt the variable to manage the different sizes of rows and columns… maybe in another article!

In place rotation

We’ve seen how to rotate the matrix, but the job is not done yet: we still have to answer the second part. What about rotating the matrix in place? To be clear, rotating in place (or, in general, applying a function in place) means applying the rotation directly on the input instance: we are not allowed to use any other space (or just a small additional constant space) to accomplish the task. We need to modify directly the given matrix and its elements to rotate it.

How? Let’s think about what we have done before: we swapped the rows for the columns. Our operation is really similar to the mathematical operation of transposition, defined as the following:

Basically, for each element in A in position ( i, j ), the transposed matrix Aᵗ contains the same element but in position ( i,j ). Obviously, the elements on the diagonal of the matrix will remain in the same place. So, for example, transposing the little matrix of the above example goes like this:

As you can see, rows and columns get swapped with this operation. We are not quite there, though, because the columns are not in the right order. Reordering them is not a difficult job, though. We simply reverse each row, and our job is done.

Let’s give it a try, then.

The code (in place)

https://gist.github.com/NicolaM94/e053a95c65012cbe0c0a52d377f26654?embedable=true#file-main-go

The code for this one is a bit longer, but don’t worry: we’ll break it apart as always. Let’s start from the Transpose function. This function applies what we have done manually before: for each row, we take the elements to the right of the diagonal and swap them with their corresponding element below the diagonal. We use temp as temporary storage for the element i,j, swap i,j with j,i and swap j,i with temp . After that, we simply return the matrix.

Now, we need a way to reverse the rows, which is done with the invertArray function and the InvertRows function. We need to write an invertArray function since Go does not have a built-in method to do so. To do this, we use the same approach as in the transpose function on a single array: we walk over the array from the first to its middle element and swap each element with its corresponding element starting from the end of the array. For instance, an array of length 5 will have indexes from 0 to 4, and we’ll exchange element 0 with element 4, element 1 with element 3 and element 2 will stay in place.

The invertRows is simply a wrapper for the invertArray function: it applies this last function to all the rows in the matrix. And finally, we wrap everything again with the last function RotateClockWiseIP . Again, what happens here, taking the first matrix as an example, is:

[[1,2],[3,4]] -> [[1,3],[2,4]] -> [[3,1],[4,2]]

Time complexity

As always, let’s take a brief moment to discuss the complexity of the algorithm. As always, most of the time spent by both algorithms is spent inside the for loops. Both algorithms have inner for loops, too, so the time spent grows quadratically to O(n²). This is pretty obvious if you think about it: having a matrix of size N*N means having N² elements to pass on. And even if the second algorithm only walks half of the elements of both the array and the matrix, at best, we’ll have a time complexity of O(N²/2). But since we skip over multiplicative constants in time complexity evaluation, we would still be back to O(N²).

Conclusions

Here’s the algorithm. What do you think about it? Let me know in the comments if you have a better version for this one!

Many thanks for reading and supporting the blog. If you also would like to contribute with coffee, here’s my Ko-fi page where you can support even more!

As always, thanks for reading.

Nicola

Also published here.