# Leetcode 48 : Rotate Image

Problem Statement :

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.

Test Cases :

## Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

## Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

## Example 3:

Input: matrix = []
Output: []
Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints:

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

Algorithm :

The simple idea is, consider this matrix

`matrix = [[1,2,3],[4,5,6],[7,8,9]]1 2 34 5 67 8 9Just take the transpose and lets see what we got :1 2 3      1 4 74 5 6. =>  2 5 8 7 8 9      3 6 9`

So we got the above after doing the transpose operation.

`for (int i=0; i<row; i++) { for (int j=0; j<i; j++) {     swap(matrix, i, j);  } }Now let’s compare it with our possible answer.Our transpose is :1 4 7                    7 4 12 5 8. and our answer is 8 5 23 6 9                    9 6 3`

So what we observe, answer is just reversing each row after doing the transpose.

`1 4 7.after reversing  7 4 12 5 8 after reversing  8 5 23 6 9 after reversing  9 6 3`

which is what we needed as our answer.

So algorithm is pretty simple :

1) Take the transpose of the given matrix
2) Reverse each row

`Note : The above is 90 degree clockwise direction. What if, we need to rotate 90 degree anti clockwise direction.Same way, just take the transpose.1 2 3     1 4 74 5 6. => 2 5 8 7 8 9     3 6 9`

Now what will be our possible answer if we do anti clockwise 90 degree rotation on given matrix.

`1 2 3     3 6 94 5 6. => 2 5 8 7 8 9     1 4 7`

Now we can just observe the answer along with the transpose of the matrix

`1 4 7                    3 6 92 5 8. and our answer is 2 5 83 6 9                    1 4 7`

So we can observe that if we just reverse all the column, we will get the desired output.

`1 4 7. after reversing column wise 3 6 92 5 8                              2 5 83 6 9                              1 4 7````

Complexity :

Time complexity is O(row * col) and since we are doing in-place, space complexity is O(1).

Code : (Clockwise 90 degree rotation)

`class Solution { public void rotate(int[][] matrix) { if (matrix == null || matrix.length == 0) { return; } int row = matrix.length; int col = matrix.length; for (int i=0; i<row; i++) { for (int j=0; j<i; j++) { swap(matrix, i, j); } } for (int [] rowWise : matrix) { reverse(rowWise, 0, col — 1); } }  private void swap(int [][] matrix, int i, int j) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; }  private void reverse(int [] nums, int i, int j) { while (i < j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; j — ; } }}`

--

-- ## Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.