Rotate Square Matrix by 90 Degrees Counterclockwise

Given a square matrix mat[][], rotate it 90 degrees counterclockwise, modifying the original matrix directly.

Examples: 

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

Explanation: Each element is moved to its new position based on a 90-degree counter clockwise rotation.

Input: mat[][] = [[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: Each element is moved to its new position based on a 90-degree counter clockwise rotation.

[Naive Approach] Using Extra Space - O(n^2) Time and O(n^2) Space

We mainly need to move first row elements to first column in reverse order, second row elements to second column in reverse order and so on.

Let us first try to find out a pattern to solve the problem for n = 4 (second example matrix above)

• mat[0][0] goes to mat[3][0]
• mat[0][1] goes to mat[2][0]
• mat[1][0] goes to mat[3][1]
• mat[3][3] goes to mat[0][3]

Do you see a pattern? Mainly we need to move mat[i][j] to mat[n-j-1][i]. We first move elements in a temporary matrix, then copy the temporary to the original. If we directly copy elements within the matrix, it would cause data loss.

#include <iostream>
#include <vector>
using namespace std;

void rotateMatrix(vector<vector<int>>& mat) {
    int n = mat.size();
    vector<vector<int>> res(n, vector<int>(n));
  
    // Rotate the matrix 90 degrees counterclockwise
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            res[n - j - 1][i] = mat[i][j];
        }
    }

    // Copy the rotated matrix back
    // to the original matrix
    mat = res;
}

int main() {
    vector<vector<int>> mat = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    rotateMatrix(mat);

    for (auto& row : mat) {
        for (int x : row) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}

#include <stdio.h>

void rotateMatrix(int n, int mat[n][n]) {
    int res[n][n];

    // Rotate the matrix 90 degrees counterclockwise
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            res[n - j - 1][i] = mat[i][j];
        }
    }

    // Copy the rotated matrix back to the original matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            mat[i][j] = res[i][j];
        }
    }
}

int main() {
    int n = 4;
    int mat[4][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    rotateMatrix(n, mat);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }

    return 0;
}

class GfG {
    static void rotateMatrix(int[][] mat) {
        int n = mat.length;
        int[][] res = new int[n][n];

        // Rotate the matrix 90 degrees counterclockwise
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res[n - j - 1][i] = mat[i][j];
            }
        }

        // Copy the rotated matrix back to the original matrix
        for (int i = 0; i < n; i++) {
            System.arraycopy(res[i], 0, mat[i], 0, n);
        }
    }

    public static void main(String[] args) {
        int[][] mat = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };

        rotateMatrix(mat);

        // Print the rotated matrix
        for (int[] row : mat) {
            for (int x : row) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
}

def rotateMatrix(mat):
    n = len(mat)
    res = [[0] * n for _ in range(n)]

    # Rotate the matrix 90 degrees counterclockwise
    for i in range(n):
        for j in range(n):
            res[n - j - 1][i] = mat[i][j]

    # Copy the rotated matrix back to the original matrix
    for i in range(n):
        for j in range(n):
            mat[i][j] = res[i][j]

if __name__ == "__main__":
  mat = [[1, 2, 3, 4],
         [5, 6, 7, 8],
         [9, 10, 11, 12],
         [13, 14, 15, 16]]

  rotateMatrix(mat)

  for row in mat:
    print(" ".join(map(str, row)))

using System;

class GfG {
    static void rotateMatrix(int[][] mat) {
        int n = mat.Length;
        int[][] res = new int[n][];
        for (int i = 0; i < n; i++) {
            res[i] = new int[n];
        }

        // Rotate the matrix 90 degrees counterclockwise
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res[n - j - 1][i] = mat[i][j];
            }
        }

        // Copy the result matrix back to original matrix
        for (int i = 0; i < n; i++) {
            Array.Copy(res[i], mat[i], n);
        }
    }

    public static void Main() {
        int[][] mat = {
            new int[] {1, 2, 3, 4},
            new int[] {5, 6, 7, 8},
            new int[] {9, 10, 11, 12},
            new int[] {13, 14, 15, 16}
        };

        rotateMatrix(mat);

        for (int i = 0; i < mat.Length; i++) {
            for (int j = 0; j < mat[i].Length; j++) {
                Console.Write(mat[i][j] + " ");
            }
            Console.WriteLine();
        }
    }
}

function rotateMatrix(mat) {
    const n = mat.length;

    const res = Array.from({ length: n }, () => Array(n).fill(0));

    // Rotate the matrix 90 degrees counterclockwise
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            res[n - j - 1][i] = mat[i][j];
        }
    }

    // Copy the result matrix back to original matrix
    for (let i = 0; i < n; i++) {
        mat[i] = res[i].slice();
    }
}

// Driver code
const mat = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
];

rotateMatrix(mat);

for (const row of mat) {
    console.log(row.join(' '));
}

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

[Expected Approach 1] Forming Cycles - O(n²) Time and O(1) Space

To solve the question without any extra space, rotate the array in form of cycles. For example, a 4 X 4 matrix will have 2 cycles. The first cycle is formed by its 1st row, last column, last row, and 1st column. The second cycle is formed by the 2nd row, second-last column, second-last row, and 2nd column. The idea is for each square cycle, to swap the elements involved with the corresponding cell in the matrix in an anticlockwise direction i.e. from top to left, left to bottom, bottom to right, and from right to top one at a time using nothing but a temporary variable to achieve this.

Step By Step Algorithm:

• There are n/2 squares or cycles in a matrix of side n. Process one square at a time. Use a loop to traverse the matrix cycle by cycle, i.e., loop from 0 to n/2−1, where the loop counter is i.
• Consider elements in group of 4 in current square and rotate the four elements at a time.
• Now run a loop in each cycle from i to n - i - 1 where the loop counter is j.
• The elements in the current group are P1 (i, j), P2 (j, n-1-i), P3 (n-1-i, n-1-j) and P4 (n-1-j, i), now rotate these 4 elements, i.e. temp <- P1, P1 <- P2, P2<- P3, P3<- P4, P4<-temp.

#include <iostream>
#include <vector>
using namespace std;

void rotateMatrix(vector<vector<int>> &mat){
  	int n = mat.size();
  
    // Consider all cycles one by one
    for (int i = 0; i < n / 2; i++) {
      
        // Consider elements in group of 4 
        // as P1, P2, P3 & P4 in current square
        for (int j = i; j < n - i - 1; j++) {
          	
            int temp = mat[i][j];
            mat[i][j] = mat[j][n - 1 - i];
            mat[j][n - 1 - i] = mat[n - 1 - i][n - 1 - j];
            mat[n - 1 - i][n - 1 - j] = mat[n - 1 - j][i];
            mat[n - 1 - j][i] = temp;
        }
    }
}

int main() {
    vector<vector<int>> mat = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    rotateMatrix(mat);
    for (auto& row : mat) {
        for (int x : row) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}

#include <stdio.h>

void rotateMatrix(int n, int mat[n][n])
{
    // Consider all cycles one by one
    for (int i = 0; i < n / 2; i++)
    {
        // Consider elements in group of 4
        for (int j = i; j < n - i - 1; j++)
        {
            int temp = mat[i][j];
            mat[i][j] = mat[j][n - 1 - i];
            mat[j][n - 1 - i] = mat[n - 1 - i][n - 1 - j];
            mat[n - 1 - i][n - 1 - j] = mat[n - 1 - j][i];
            mat[n - 1 - j][i] = temp;
        }
    }
}

int main()
{
    int n = 4;
    int mat[4][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};

    rotateMatrix(n, mat);

    // Print rotated matrix
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }

    return 0;
}

class GfG {
    static void rotateMatrix(int[][] mat) {
        int n = mat.length;

        // Consider all cycles one by one
        for (int i = 0; i < n / 2; i++) {

            // Consider elements in group of 4
            // as P1, P2, P3 & P4 in current square
            for (int j = i; j < n - i - 1; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][n - 1 - i];
                mat[j][n - 1 - i] = mat[n - 1 - i][n - 1 - j];
                mat[n - 1 - i][n - 1 - j] = mat[n - 1 - j][i];
                mat[n - 1 - j][i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] mat = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };

        rotateMatrix(mat);

        // Print the rotated matrix
        for (int[] row : mat) {
            for (int x : row) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
}

def rotateMatrix(mat):
    n = len(mat)

    # Consider all cycles one by one
    for i in range(n // 2):
        
        # Consider elements in group of 4
        # as P1, P2, P3 & P4 in current square
        for j in range(i, n - i - 1):

            temp = mat[i][j]
            mat[i][j] = mat[j][n - 1 - i]
            mat[j][n - 1 - i] = mat[n - 1 - i][n - 1 - j]
            mat[n - 1 - i][n - 1 - j] = mat[n - 1 - j][i]
            mat[n - 1 - j][i] = temp

if __name__ == "__main__":
    mat = [[1, 2, 3, 4],
           [5, 6, 7, 8],
           [9, 10, 11, 12],
           [13, 14, 15, 16]]

    rotateMatrix(mat)

    for row in mat:
      print(" ".join(map(str, row)))

using System;

class GfG {
    static void rotateMatrix(int[][] mat) {
        int n = mat.Length;

        // Consider all cycles one by one
        for (int i = 0; i < n / 2; i++) {
            
            // Consider elements in group of 4
            // as P1, P2, P3 & P4 in current square
            for (int j = i; j < n - i - 1; j++) {

                int temp = mat[i][j];
                mat[i][j] = mat[j][n - 1 - i];
                mat[j][n - 1 - i] = mat[n - 1 - i][n - 1 - j];
                mat[n - 1 - i][n - 1 - j] = mat[n - 1 - j][i];
                mat[n - 1 - j][i] = temp;
            }
        }
    }

     static void Main() {
        int[][] mat = {
            new int[] {1, 2, 3, 4},
            new int[] {5, 6, 7, 8},
            new int[] {9, 10, 11, 12},
            new int[] {13, 14, 15, 16}
        };

        rotateMatrix(mat);

        for (int i = 0; i < mat.Length; i++) {
            for (int j = 0; j < mat[i].Length; j++) {
                Console.Write(mat[i][j] + " ");
            }
            Console.WriteLine();
        }
    }
}

function rotateMatrix(mat) {
    const n = mat.length;

    // Consider all cycles one by one
    for (let i = 0; i < n / 2; i++) {
        
        // Consider elements in group of 4
        // as P1, P2, P3 & P4 in current square
        for (let j = i; j < n - i - 1; j++) {

            let temp = mat[i][j];
            mat[i][j] = mat[j][n - 1 - i];
            mat[j][n - 1 - i] = mat[n - 1 - i][n - 1 - j];
            mat[n - 1 - i][n - 1 - j] = mat[n - 1 - j][i];
            mat[n - 1 - j][i] = temp;
        }
    }
}

// Driver code
const mat = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
];

rotateMatrix(mat);

for (const row of mat) {
    console.log(row.join(" "));
}

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

[Expected Approach 2] Reversing Rows and Transposing - O(n²) Time and O(1) Space

Rotating a square matrix 90 degrees counterclockwise, each element moves to a new position. The top row becomes the left most column in reverse order, the second row becomes the second-left most column in reverse order, and so on. By first reversing the rows, you rearrange the elements in such a way that when you transpose them, they end up in their final rotated positions.

Follow the given steps to solve the problem:

• Reverse every individual row of the matrix
• Perform Transpose of the matrix

Note: We can also rotate the matrix by first performing the transpose and then reversing every column of the matrix.

• Clockwise 90° Rotation: Transpose the matrix, then reverse each row.
• Counterclockwise 90° Rotation: Reverse each row, then transpose the matrix.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void rotateMatrix(vector<vector<int>> &mat){ 
  	int n = mat.size();
  	
  	// Reverse each row
    for (int i = 0; i < n; i++)
        reverse(mat[i].begin(), mat[i].end());

    // Performing Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++)
            swap(mat[i][j], mat[j][i]);
    }
}

int main() {
    vector<vector<int>> mat = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    rotateMatrix(mat);
    for (auto& row : mat) {
        for (int x : row) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}

#include <stdio.h>

// Function to reverse a row
void reverseRow(int n, int row[]) {
    int start = 0, end = n - 1;
    while (start < end) {
        int temp = row[start];
        row[start] = row[end];
        row[end] = temp;
        start++;
        end--;
    }
}

// Function to rotate the matrix
void rotateMatrix(int n, int mat[n][n]) {
    // Step 1: Reverse each row
    for (int i = 0; i < n; i++) {
        reverseRow(n, mat[i]);
    }

    // Step 2: Transpose the matrix
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = temp;
        }
    }
}

int main() {
    int n = 4;
    int mat[4][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    rotateMatrix(n, mat);

    // Print rotated matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }

    return 0;
}

class GfG {
    static void rotateMatrix(int[][] mat) {
        int n = mat.length;
        
        // Reverse each row
        for (int i = 0; i < n; i++) {
            int start = 0, end = n - 1;
            while (start < end) {
                int temp = mat[i][start];
                mat[i][start] = mat[i][end];
                mat[i][end] = temp;
                start++;
                end--;
            }
        }

        // Performing Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] mat = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };

        rotateMatrix(mat);

        // Print the rotated matrix
        for (int[] row : mat) {
            for (int x : row) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
}

def rotateMatrix(mat):
    n = len(mat)
    
    # Reverse each row
    for row in mat:
        row.reverse()

    # Performing Transpose
    for i in range(n):
        for j in range(i + 1, n):
            mat[i][j], mat[j][i] = mat[j][i], mat[i][j]

if __name__ == "__main__":
    mat = [[1, 2, 3, 4],
           [5, 6, 7, 8],
           [9, 10, 11, 12],
           [13, 14, 15, 16]]

    rotateMatrix(mat)

    for row in mat:
      print(" ".join(map(str, row)))

using System;

class GfG {
    static void rotateMatrix(int[][] mat) {
        int n = mat.Length;

        // Reverse each row
        for (int i = 0; i < n; i++) {
            Array.Reverse(mat[i]);
        }

        // Performing Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
    }

     static void Main() {
        int[][] mat = {
            new int[] {1, 2, 3, 4},
            new int[] {5, 6, 7, 8},
            new int[] {9, 10, 11, 12},
            new int[] {13, 14, 15, 16}
        };

        rotateMatrix(mat);

        for (int i = 0; i < mat.Length; i++) {
            for (int j = 0; j < mat[i].Length; j++) {
                Console.Write(mat[i][j] + " ");
            }
            Console.WriteLine();
        }
    }
}

function rotateMatrix(mat) {
    const n = mat.length;

    // Reverse each row
    for (let i = 0; i < n; i++) {
        mat[i].reverse();
    }

    // Performing Transpose
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [mat[i][j], mat[j][i]] = [mat[j][i], mat[i][j]];
        }
    }
}

// Driver code
const mat = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
];

rotateMatrix(mat);

for (const row of mat) {
    console.log(row.join(" "));
}

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