Rotate a matrix by 90 degree without using any extra space | Set 2

Given a square matrix, turn it by 90 degrees in anti-clockwise direction without using any extra space.

Examples:

```Input
1  2  3
4  5  6
7  8  9
Output:
3  6  9
2  5  8
1  4  7

Input:
1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16
Output:
4  8 12 16
3  7 11 15
2  6 10 14
1  5  9 13```

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

An approach that requires extra space is already discussed in below set:
Inplace rotate square matrix by 90 degrees | Set 1

In this post another approach is discussed which is much simpler than the above approach.

There are two steps :

1. Find transpose of matrix.
2. Reverse columns of the transpose.

Illustration of above steps :

```Let the given matrix be
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

First we find transpose.
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

Then we reverse elements of every column.
4 8 12 16
3 7 11 15
2 6 10 14
1 5  9 13
```

Below is the implementation of above steps.

C++

 `// C++ program for left rotation of matrix by 90 ` `// degree without using extra space ` `#include ` `using` `namespace` `std; ` `#define R 4 ` `#define C 4 ` ` `  `// After transpose we swap elements of column ` `// one by one for finding left rotation of matrix ` `// by 90 degree ` `void` `reverseColumns(``int` `arr[R][C]) ` `{ ` `    ``for` `(``int` `i = 0; i < C; i++) ` `        ``for` `(``int` `j = 0, k = C - 1; j < k; j++, k--) ` `            ``swap(arr[j][i], arr[k][i]); ` `} ` ` `  `// Function for do transpose of matrix ` `void` `transpose(``int` `arr[R][C]) ` `{ ` `    ``for` `(``int` `i = 0; i < R; i++) ` `        ``for` `(``int` `j = i; j < C; j++) ` `            ``swap(arr[i][j], arr[j][i]); ` `} ` ` `  `// Function for print matrix ` `void` `printMatrix(``int` `arr[R][C]) ` `{ ` `    ``for` `(``int` `i = 0; i < R; i++) { ` `        ``for` `(``int` `j = 0; j < C; j++) ` `            ``cout << arr[i][j] << ``" "``; ` `        ``cout << ````' '````; ` `    ``} ` `} ` ` `  `// Function to anticlockwise rotate matrix ` `// by 90 degree ` `void` `rotate90(``int` `arr[R][C]) ` `{ ` `    ``transpose(arr); ` `    ``reverseColumns(arr); ` `} ` ` `  `// Driven code ` `int` `main() ` `{ ` `    ``int` `arr[R][C] = { { 1, 2, 3, 4 }, ` `                      ``{ 5, 6, 7, 8 }, ` `                      ``{ 9, 10, 11, 12 }, ` `                      ``{ 13, 14, 15, 16 } }; ` `    ``rotate90(arr); ` `    ``printMatrix(arr); ` `    ``return` `0; ` `} `

Java

 `// JAVA Code for left Rotation of a ` `// matrix by 90 degree without using ` `// any extra space ` `import` `java.util.*; ` ` `  `class` `GFG { ` ` `  `    ``// After transpose we swap elements of ` `    ``// column one by one for finding left ` `    ``// rotation of matrix by 90 degree ` `    ``static` `void` `reverseColumns(``int` `arr[][]) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < arr[``0``].length; i++) ` `            ``for` `(``int` `j = ``0``, k = arr[``0``].length - ``1``; ` `                 ``j < k; j++, k--) { ` `                ``int` `temp = arr[j][i]; ` `                ``arr[j][i] = arr[k][i]; ` `                ``arr[k][i] = temp; ` `            ``} ` `    ``} ` ` `  `    ``// Function for do transpose of matrix ` `    ``static` `void` `transpose(``int` `arr[][]) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < arr.length; i++) ` `            ``for` `(``int` `j = i; j < arr[``0``].length; j++) { ` `                ``int` `temp = arr[j][i]; ` `                ``arr[j][i] = arr[i][j]; ` `                ``arr[i][j] = temp; ` `            ``} ` `    ``} ` ` `  `    ``// Function for print matrix ` `    ``static` `void` `printMatrix(``int` `arr[][]) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < arr.length; i++) { ` `            ``for` `(``int` `j = ``0``; j < arr[``0``].length; j++) ` `                ``System.out.print(arr[i][j] + ``" "``); ` `            ``System.out.println(``""``); ` `        ``} ` `    ``} ` ` `  `    ``// Function to anticlockwise rotate ` `    ``// matrix by 90 degree ` `    ``static` `void` `rotate90(``int` `arr[][]) ` `    ``{ ` `        ``transpose(arr); ` `        ``reverseColumns(arr); ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[][] = { { ``1``, ``2``, ``3``, ``4` `}, ` `                        ``{ ``5``, ``6``, ``7``, ``8` `}, ` `                        ``{ ``9``, ``10``, ``11``, ``12` `}, ` `                        ``{ ``13``, ``14``, ``15``, ``16` `} }; ` ` `  `        ``rotate90(arr); ` `        ``printMatrix(arr); ` `    ``} ` `} ` ` `  `// This code is contributed by Arnav Kr. Mandal. `

C#

 `// C# program for left rotation ` `// of matrix by 90 degree ` `// without using extra space ` `using` `System; ` ` `  `class` `GFG { ` `    ``static` `int` `R = 4; ` `    ``static` `int` `C = 4; ` ` `  `    ``// After transpose we swap ` `    ``// elements of column one ` `    ``// by one for finding left ` `    ``// rotation of matrix by ` `    ``// 90 degree ` `    ``static` `void` `reverseColumns(``int``[, ] arr) ` `    ``{ ` `        ``for` `(``int` `i = 0; i < C; i++) ` `            ``for` `(``int` `j = 0, k = C - 1; ` `                 ``j < k; j++, k--) { ` `                ``int` `temp = arr[j, i]; ` `                ``arr[j, i] = arr[k, i]; ` `                ``arr[k, i] = temp; ` `            ``} ` `    ``} ` ` `  `    ``// Function for do ` `    ``// transpose of matrix ` `    ``static` `void` `transpose(``int``[, ] arr) ` `    ``{ ` `        ``for` `(``int` `i = 0; i < R; i++) ` `            ``for` `(``int` `j = i; j < C; j++) { ` `                ``int` `temp = arr[j, i]; ` `                ``arr[j, i] = arr[i, j]; ` `                ``arr[i, j] = temp; ` `            ``} ` `    ``} ` ` `  `    ``// Function for print matrix ` `    ``static` `void` `printMatrix(``int``[, ] arr) ` `    ``{ ` ` `  `        ``for` `(``int` `i = 0; i < R; i++) { ` `            ``for` `(``int` `j = 0; j < C; j++) ` `                ``Console.Write(arr[i, j] + ``" "``); ` `            ``Console.WriteLine(``""``); ` `        ``} ` `    ``} ` ` `  `    ``// Function to anticlockwise ` `    ``// rotate matrix by 90 degree ` `    ``static` `void` `rotate90(``int``[, ] arr) ` `    ``{ ` `        ``transpose(arr); ` `        ``reverseColumns(arr); ` `    ``} ` ` `  `    ``// Driver code ` `    ``static` `void` `Main() ` `    ``{ ` `        ``int``[, ] arr = { { 1, 2, 3, 4 }, ` `                        ``{ 5, 6, 7, 8 }, ` `                        ``{ 9, 10, 11, 12 }, ` `                        ``{ 13, 14, 15, 16 } }; ` ` `  `        ``rotate90(arr); ` `        ``printMatrix(arr); ` `    ``} ` ` `  `    ``// This code is contributed ` `    ``// by Sam007 ` `} `

Python 3

 `# Python 3 program for left rotation of matrix by 90 ` `# degree without using extra space ` ` `  `R ``=` `4` `C ``=` `4` `  `  `# After transpose we swap elements of column ` `# one by one for finding left rotation of matrix ` `# by 90 degree ` `def` `reverseColumns(arr): ` `    ``for` `i ``in` `range``(C): ` `        ``j ``=` `0` `        ``k ``=` `C``-``1` `        ``while` `j < k: ` `            ``t ``=` `arr[j][i] ` `            ``arr[j][i] ``=` `arr[k][i] ` `            ``arr[k][i] ``=` `t ` `            ``j ``+``=` `1` `            ``k ``-``=` `1` `   `  `# Function for do transpose of matrix ` `def` `transpose(arr): ` `    ``for` `i ``in` `range``(R): ` `        ``for` `j ``in` `range``(i, C): ` `            ``t ``=` `arr[i][j] ` `            ``arr[i][j] ``=` `arr[j][i] ` `            ``arr[j][i] ``=` `t ` `  `  `# Function for print matrix ` `def` `printMatrix(arr): ` `    ``for` `i ``in` `range``(R): ` `        ``for` `j ``in` `range``(C): ` `            ``print``(``str``(arr[i][j]), end ``=``" "``) ` `        ``print``() ` `  `  `# Function to anticlockwise rotate matrix ` `# by 90 degree ` `def` `rotate90(arr): ` `    ``transpose(arr) ` `    ``reverseColumns(arr) ` `  `  `# Driven code ` `arr ``=` `[[``1``, ``2``, ``3``, ``4``], ` `        ``[``5``, ``6``, ``7``, ``8``], ` `        ``[``9``, ``10``, ``11``, ``12``], ` `        ``[``13``, ``14``, ``15``, ``16``] ` `    ``]; ` `rotate90(arr) ` `printMatrix(arr) `

PHP

 ` `

Output:

```4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
```

Time complexity :O(R*C)
Space complexity :O(1)

The above steps/program do left (or anticlockwise) rotation, how to right (or clockwise) rotate?
To right rotate, we do following steps.

1. Find transpose of matrix.
2. Reverse rows of the transpose.

Illustration of above steps :

```Let the given matrix be
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

First we find transpose.
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

Then we reverse elements of every row.
13  9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
```

tags:

Matrix rotation Matrix