# Rotate Matrix anti-clockwise by 90 degree

Problem statement: Given a matrix, your task is to rotate matrix anti-clockwise by 90 degrees.

Examples:

```Example 1:
Input:   {{1,2,3},
{4,5,6},
{7,8,9}}
Output:
3 6 9
2 5 8
1 4 7
Explanation: Rotate the matrix anti-clockwise by 90 degrees and return it.

Example 2:
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
Explanation: Rotate the matrix anti-clockwise by 90 degrees and return it.
```

### Solution:

DisclaimerDon’t jump directly to the solution, try it out yourself first.

Solution 1: Brute force

Intuition & Approach: Take one temporary matrix of size n*n and replace the elements accordingly.

For example:

Let’s consider matrix [1,2,3] , [4,5,6],[7,8,9] and its output is

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

So by observing it is clear that:

• Element at index 0,0 is replaced by the element at index 0,2
• Element at index 0,1 is replaced by the element at index 1,2
• Element at index 0,2 is replaced by the element at index 2,2
• Element at index 1,0 is replaced by the element at index 0,1
• Element at index 1,1 is replaced by the element at index 1,1
• Element at index 1,2 is replaced by the element at index 2,1
• Element at index 2,0 is replaced by the element at index 0,0
• Element at index 2,1 is replaced by the element at index 1,0
• Element at index 2,2 is replaced by the element at index 2,0

Here every row and column is following a pattern so, according to the above pattern we will replace the values.

Code:

## C++ Code

``````#include<bits/stdc++.h>

using namespace std;

void rotate(int matrix[][3]) {
int n = 3;

//Creating new matrix to store rotated values
int temp[n][n];

int ind = n - 1;
for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {
temp[i][j] = matrix[j][ind];
}
ind--;
}
//Printing array after rotation
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << temp[i][j] << " ";
}
cout << endl;
}
}
int main() {
int matrix[][3] = {{1,2,3},{4,5,6},{7,8,9}};

rotate(matrix);

}``````

Output:

3 6 9
2 5 8
1 4 7

Time complexity: O(n*n) for traversing in matrix

Space complexity: O(n*n) for temporary matrix

## Java Code

``````public class TUF {
private static void rotate(int[][] matrix) {
int n = matrix.length;

//Creating new matrix to store rotated values
int temp[][] = new int[n][n];

int ind = n - 1;
for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {
temp[i][j] = matrix[j][ind];
}
ind--;
}
//Printing array after rotation
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(temp[i][j] + " ");
}
System.out.println();
}
}

public static void main(String[] args) {
int matrix[][] = {{1,2,3},{4,5,6},{7,8,9}};
int n = matrix.length;

rotate(matrix);

}
}``````

Output:

3 6 9
2 5 8
1 4 7

Time complexity: O(n*n) for traversing in matrix

Space complexity: O(n*n) for temporary matrix

### Intuition:

We can see that the first column is the reverse of the first row, so that’s why we can find the transpose of the matrix and reverse each column.

### Approach:

1. Find the transpose of the matrix.
2. Reverse every column of the matrix.

Code:

## C++ Code

``````#include<bits/stdc++.h>

using namespace std;

void rotate(int matrix[][3]) {
int n = 3;

/* Finding transpose*/
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}

/* Reverse every column */
int ind = n - 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[j][i];
matrix[j][i] = matrix[ind][i];
matrix[ind][i] = temp;
ind--;
}
ind = n - 1;
}

//Printing array after rotation
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
int matrix[][3] = {{1,2,3},{4,5,6},{7,8,9}};

rotate(matrix);

}``````

Output:

3 6 9
2 5 8
1 4 7

Time complexity: O(n*n) +O(n*n), for transpose and reversing.

Space complexity: O(1) as we are not using any extra space.

## Java Code

``````public class TUF {
private static void rotate(int[][] matrix) {
int n = matrix.length;

/* Finding transpose*/
for (int i=0;i<n;i++){
for (int j=i+1;j<n;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}

/* Reverse every column */
int ind = n-1;
for (int i=0;i<n;i++){
for (int j=0;j<n/2;j++){
int temp = matrix[j][i];
matrix[j][i] = matrix[ind][i];
matrix[ind][i] = temp;
ind--;
}
ind = n-1;
}

//Printing array after rotation
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}

public static void main(String[] args) {
int matrix[][] = {{1,2,3},{4,5,6},{7,8,9}};
int n = matrix.length;

rotate(matrix);

}
}
``````

Output:

3 6 9
2 5 8
1 4 7

Time complexity: O(n*n) +O(n*n), for transpose and reversing.

Space complexity: O(1) as we are not using any extra space.