loading...

Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees

alisabaj profile image Alisa Bajramovic Updated on ・6 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm is the Rotate Image problem:

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

For example, if you were given the 2D array

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

rotating the array 90 degrees clockwise would give us the output of

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

Put another way, the first row becomes the last column, the second row becomes the middle column, and the last row becomes the first column.

![Three sets of images. In the first set, there's a 2D array, [[1,2,3], [4,5,6],[7,8,9]], and the first row is highlighted in cyan. There's a blue arrow turned 90 degrees clockwise, and next to it is another 2D array, [[, 1], [, 2],[, , 3]]. The last column is highlighted in cyan. In the second set, there's a 2D array, [[1,2,3], [4,5,6],[7,8,9]], whose second row is highlighted in cyan. There's a blue arrow turned 90 degrees clockwise, and next to it is another 2D array, [[, 4, 1], [, 5, 2], [, 6, 3]], whose second column is highlighted in cyan. In the third set of images, there's a 2D array, [[1,2,3], [4,5,6], [7,8,9]], and the last row is highlighted in cyan. There's a blue arrow turned 90 degrees clockwise, and next to it is another 2D array, [[7, 4, 1], [8, 5, 2], [9, 6, 3]], whose second column is highlighted in cyan. ](https://dev-to-uploads.s3.amazonaws.com/i/bluo1pumyica1dmly0qz.png)

In this post, I'll start by discussing my approach to solving this problem, then I'll code the solution using JavaScript.

Approaching the Rotating 2D Array Problem

Not long ago, I discussed the problem of rotating a one dimensional array (you can find that post here). What's trickier about a 2D array is that you have to keep track of both the row and the column that we're in.

The way I'll be rotating the 2d array (also known as a matrix) is with a two step approach. First, I'll transpose the matrix, which means switching the rows with the columns. Then, I'll reverse the elements in each row.

Let's say our inputted matrix was

[
  [1, 2],
  [3, 4]
]

After transposing the matrix, it would look like this:

[
  [1, 3],
  [2, 4]
]

The first row became the first column, and the second row became the second column. However, we want all of these elements to be reversed, so we'll reverse each element in each row, giving us the final matrix:

[
  [3, 1],
  [4, 2]
]

which is the solution we're after.

Solving the Matrix Rotation Problem

We'll start our solution by checking for edge cases. If the matrix is empty, then there's nothing to rotate, so we can immediately return null. Additionally, because we know the matrix is square (n x n), if it has a length of 1, then it only has one element in it, so we can just return that element.

function rotate(matrix) {
  if (!matrix.length) return null;
  if (matrix.length === 1) return matrix;
  //...
}

Now, like discussed above, we'll have a two step solution. To keep the code as neat as possible, we'll separate the steps out from the original rotate function. We can create a separate function called transpose(), which will take in the matrix, and we'll call it from inside the rotate() function.

function rotate(matrix) {
  if (!matrix.length) return null;
  if (matrix.length === 1) return matrix;
  transpose(matrix);
  //...
}

function transpose(matrix) {
  //...
}

Transposing the matrix, or switching the rows and columns, will require nested for loops. The first loop will go through each row, and the second loop will go through each column. Since they're nested, we'll be able to access each element at any row, column point. We'll start the first for loop at i = 0, which is the first row, and we'll start the second for loop at j = 1, which is the second column.

function rotate(matrix) {
  if (!matrix.length) return null;
  if (matrix.length === 1) return matrix;
  transpose(matrix);
  //...
}

function transpose(matrix) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = i; j < matrix[0].length; j++) {
      //...
    }
  }
  //...
}

Inside the for loops, we'll want to swap two elements -- the value at matrix[i][j] will be swapped with the value at matrix[j][i]. To do a swap, we need a temporary variable, called temp, which enables us to store the value at one point before changing that point's value.

When the for loops are done executing, we can return the updated matrix back to rotate().

function rotate(matrix) {
  if (!matrix.length) return null;
  if (matrix.length === 1) return matrix;
  transpose(matrix);
  //...
}

function transpose(matrix) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = i; j < matrix[0].length; j++) {
      const temp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = temp;
    }
  }
  return matrix;
}

We're now done with transposing the elements, so we have to move onto the second step of this solution: reversing the elements of each row. To do this, we'll want to go through each row in matrix, and call a new function called reverse() on that row. reverse() will take in three arguments: the row we want to reverse, the starting point to reverse at (which is 0), and the ending point of the reversal (with is row.length - 1).

function rotate(matrix) {
  if (!matrix.length) return null;
  if (matrix.length === 1) return matrix;
  transpose(matrix);
  matrix.forEach((row) => {
    reverse(row, 0, row.length - 1);
  });
}

function transpose(matrix) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = i; j < matrix[0].length; j++) {
      const temp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = temp;
    }
  }
  return matrix;
}

function reverse(row, start, end) {
  //...
}

Now, in reverse(), we'll set up a while loop. The idea behind this function is to have two pointers, start and end. As long as the end pointer is larger than the start pointer, we'll want to swap the values at those two spots.

To start, therefore, we'll set up a while loop in reverse(), which will keep going as long asstart < end`.

`javascript
function rotate(matrix) {
if (!matrix.length) return null;
if (matrix.length === 1) return matrix;
transpose(matrix);
matrix.forEach((row) => {
reverse(row, 0, row.length - 1);
});
}

function transpose(matrix) {
for (let i = 0; i < matrix.length; i++) {
for (let j = i; j < matrix[0].length; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
return matrix;
}

function reverse(row, start, end) {
while (start < end) {
//...
}
//...
}
`

Just like we did in transpose(), we'll need to set up a temporary variable in order to swap the values at the start and end points.

`javascript
function rotate(matrix) {
if (!matrix.length) return null;
if (matrix.length === 1) return matrix;
transpose(matrix);
matrix.forEach((row) => {
reverse(row, 0, row.length - 1);
});
}

function transpose(matrix) {
for (let i = 0; i < matrix.length; i++) {
for (let j = i; j < matrix[0].length; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
return matrix;
}

function reverse(row, start, end) {
while (start < end) {
const temp = row[start];
row[start] = row[end];
row[end] = temp;
//...
}
//...
}
`

Once the variables are swapped, we want to bring the start and end pointers toward each other, so we'll increment start, and decrement end. Once the while loops is done executing, we can return the now reversed row to rotate().

`javascript
function rotate(matrix) {
if (!matrix.length) return null;
if (matrix.length === 1) return matrix;
transpose(matrix);
matrix.forEach((row) => {
reverse(row, 0, row.length - 1);
});
}

function transpose(matrix) {
for (let i = 0; i < matrix.length; i++) {
for (let j = i; j < matrix[0].length; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
return matrix;
}

function reverse(row, start, end) {
while (start < end) {
const temp = row[start];
row[start] = row[end];
row[end] = temp;
start++;
end--;
}
return row;
}
`

Since the problem asked us to rotate the 2D array "in place", we don't have to return anything. We already modified the original matrix, so we're done with our solution!

Let me know in the comments if you have any questions or other ideas for how to approach this problem!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide