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 Problem, which you can subscribe to here! Check it out and try to solve your daily challenge! Coding 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 : you can , adjusting the final position of its elements at the end, or , following the “border” of the matrix. two ways to visualize it literally rotate the actual image of the matrix you can imagine swapping each element to its right neighbor 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 , 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. out 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 . 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! square matrices 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, (or, in general, applying a function in place) . We need to modify directly the given matrix and its elements to rotate it. rotating 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 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 in position ( ), the transposed matrix contains the same element but in position ( ). 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: A i, j Aᵗ i,j 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 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 as temporary storage for the element , swap with and swap j,i with . After that, we simply return the matrix. Transpose temp i,j i,j j,i temp Now, we need a way to reverse the rows, which is done with the function and the function. We need to write an 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. invertArray InvertRows invertArray The is simply a wrapper for the function: it applies this last function to all the rows in the matrix. And finally, we wrap everything again with the last function . Again, what happens here, taking the first matrix as an example, is: invertRows invertArray RotateClockWiseIP [[1,2],[3,4]] -> [[1,3],[2,4]] -> [[3,1],[4,2]] You can use this same code to perform any rotation, clockwise and anti-clockwise, by any degree you want (90, 180, 270 or 360 obviously). Just swap the transpose function and the invert rows function, repeat them more than one time or both, and see what happens! 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, . 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²). so the time spent grows quadratically 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 page where you can support even more! Ko-fi As always, thanks for reading. Nicola Also published here.

Too Long; Didn't Read

Making security fun one episode at a time

Daily Coding Problem: Rotating Matrices

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Daily Coding Problem: Rotating Matrices

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES