You are given an

*n*x*n*2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

Follow up:

Could you do this in-place?

Could you do this in-place?

**Understand the question:**

The question asks for rotating an image by 90 degrees. The question has two requirements:

a. Rotate by 90 degrees in clockwise.

b. Transform in-place.

To understand the problem correctly, we can give several examples to illustrate the question.

For array [1], its transformed array is still 1

For array 1 2

3 4 ,

the transformed array is 3 1

4 2

For array 1 2 3

4 5 6

7 8 9

the transformed array is 7 4 1

8 5 2

9 6 3

So it is not very difficult to see that the transformed array is actually putting first row of the original array into last column of the transformed array, and so on.

**Out-of-place Solution:**

Out-of-place solution is very easy. Just crate a buffer to store the transformed array and copy back into the original array after the transformation.

**Code (Java):**

public class Solution { public void rotate(int[][] matrix) { if (matrix == null || matrix.length == 0) return; // n * n matrix int n = matrix.length; // Temporary buffter to store rotated image int [][] temp = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { temp[j][n - i - 1] = matrix[i][j]; } } // copy back the results for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = temp[i][j]; } } } }

**In-place Solution:**

An in-place method is to first transpose the array, then swap the elements in each row.

For example, for array

1 2 3

4 5 6

7 8 9

The transposed array is:

1 4 7

2 5 8

3 6 9

Then swap elements in each row

7 4 1

8 5 2

9 6 3

**Code (Java):**

public class Solution { public void rotate(int[][] matrix) { if (matrix == null || matrix.length < 2) return; // length of the matrix int n = matrix.length; // transpose the matrix for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; } } // swap elements for each row int mid = n / 2; for (int i = 0; i < n; i++) { for (int j = 0; j < mid; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[i][n - j - 1]; matrix[i][n - j - 1] = tmp; } } } }

**Discussion:**

The time complexity is O(n^2), which is the best we can do for this algorithm. The space complexity is O(1). Note the matrix transpose algorithm, the inner loop index j starting from i + 1. That is because we have already swapped the element before i. If j starts from 0, it will swap the elements back again.

**Another in-place solution:**

Check cc150 1.6

**Code (Java):**

public class Solution { public void rotate(int[][] matrix) { // check if matrix is null or empty or length equals to 1 if (matrix == null || matrix.length < 2) return; int n = matrix.length; for (int layer = 0; layer < n/2; layer++) { int first = layer; int last = n - layer - 1; for (int i = first; i < last; i++) { int offset = i - first; int top = matrix[first][i]; // left -> top matrix[first][i] = matrix[last - offset][first]; // bottom -> left matrix[last - offset][first] = matrix[last][last - offset]; // right -> bottom matrix[last][last - offset] = matrix[i][last]; // top - > right; matrix[i][last] = top; } } } }

**Summary:**

In this post, we learned how to rotate an array in place. The third method is very tricky. Make sure to understand the details, especially for how to calculate the indices.

## No comments:

## Post a Comment