Given an n x n matrix, how can we rotate it by 90 degrees clockwise? This is a standard algorithm problem, let’s look at a straightforward solution with visuals before we refactor and optimize our code.
Our goal is to write a function that accepts an input matrix of any n x n size and returns an output of a rotated matrix. See the example of a 3 x 3 matrix below, an array of arrays representation for our input and output.
This blog will cover the following and use a 3 x 3 matrix example:
- Visuals for each step of the matrix rotation process
- How to flip matrix on major and minor diagonal
Let’s rotate this matrix…
Comparing the input matrix and the output, the columns are now rows, but reversed. For example, the first column in the input has now become the first row in the output but reversed.
What are the steps to rotate the matrix?
To access each value in the matrix, a simple nested loop can be used.
- The matrix is flipped along the major diagonal (top left to bottom right). This will transpose the columns to be rows. This is done by swapping the values on the upper half of the diagonal with the lower half. For example, the value at [row: index 0][column: index 1] is 2 to be replaced by the value at [row: index 1][column: index 0] which is 4 and vice versa. Remember to ensure the swap only takes place one time, the inner nested loop (column index) must be initialized correctly.
Now we know how to flip along the major diagonal and rotate the matrix. Let’s take it a step further.
How to flip matrix along the minor diagonal?
The minor diagonal the from the top right to the bottom left.
This problem without the rotated matrix, may be cumbersome to solve with swapping index values. Swapping the index value along the minor diagonal is not as simple as the major diagonal.
However, with the rotated matrix in play, we can visually see the solution is simple. Just reverse (upside down) the rotated matrix! The steps are:
- Rotate matrix by 90 degrees
- Reverse order of entire matrix, flip upside down. Bottom row is now on top and so on.
Let’s look at the code. The function expressions have been isolated by different ways to manipulate the matrix.
Summary of the different functions expressions:
- Rotate matrix: flip along major diagonal then reverse each row
- Flip major diagonal: will swap each value on upper half of diagonal with lower half. To ensure the swap does not occur twice, initialize the inner loop (column index) to start at the outer loop (row index).
- Flip minor diagonal: rotate matrix then reverse entire matrix
For a deeper dive, on this solution the reference below is excellent!
To break down this solution high level:
- Reverse entire matrix
- Use outer map to get all the column index’s
- Use inner map to change each row with column values
Hope this was helpful for someone!
I am ending week 6 of Hack Reactor. My 10 month old is wildly crawling and climbing everywhere. Our exercise the last 2 weeks included solving N-Queens and learning about HTTP, REST API, mechanisms of how internet traffic is transmitted and MVC. With jQuery, we got some practice getting data from a serve without a page refresh with Parse API as the back-end. Definitely, feels like there constantly is a lot to learn!