21. Rotate by 90 degree

The problem can be found at the following link: Problem Link

Problem Description

Given a square matrix mat[][] of size n x n, rotate it by 90 degrees in an anti-clockwise direction without using any extra space.

Examples:

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

Input: mat[][] = [[1, 2], [3, 4]] Output: Rotated Matrix: [[2, 4], [1, 3]]

Constraints:

• $1 ≤ n ≤ 10^2$

• $0 ≤ mat[i][j] ≤ 10^3$

My Approach

1. In-Place Transposition and Column Reversal:

   • The matrix can be rotated by performing two operations:

     1. Transpose the matrix: Swap mat[i][j] and mat[j][i] for all i, j where i < j.

     2. Reverse each column of the matrix: For each column, swap elements from the top and bottom.

2. Steps:

   • First, transpose the matrix to convert rows into columns.

   • Then, reverse each column to achieve the desired 90-degree rotation in anti-clockwise direction.

   • No extra space is used, and the operations are performed in-place.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n²), where n is the size of the matrix. The algorithm involves transposing the matrix (O(n²) operations) and then reversing each column (O(n²) operations).

• Expected Auxiliary Space Complexity: O(1), as all operations are performed in-place, and no additional space is used.

Code (C)

void rotateby90(int n, int mat[][n]) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = temp;
        }
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0, k = n - 1; i < k; i++, k--) {
            int temp = mat[i][j];
            mat[i][j] = mat[k][j];
            mat[k][j] = temp;
        }
    }
}

Code (Cpp)

class Solution {
public:
    void rotateby90(vector<vector<int>>& mat) {
        int n = mat.size();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                swap(mat[i][j], mat[j][i]);
            }
        }
        reverse(mat.begin(), mat.end());
    }
};

👨‍💻 Alternative Approaches

Code (Cpp)

class Solution {
public:
    void rotateby90(vector<vector<int>>& mat) {
        int n = mat.size();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                swap(mat[i][j], mat[j][i]);
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0, k = n - 1; i < k; i++, k--) {
                swap(mat[i][j], mat[k][j]);
            }
        }
    }
};

Code (Java)

class Solution {
    static void rotateby90(int mat[][]) {
        int n = mat.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0, k = n - 1; i < k; i++, k--) {
                int temp = mat[i][j];
                mat[i][j] = mat[k][j];
                mat[k][j] = temp;
            }
        }
    }
}

Code (Python)

class Solution:
    def rotateby90(self, mat):
        n = len(mat)
        for i in range(n):
            for j in range(i, n):
                mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
        for j in range(n):
            i, k = 0, n - 1
            while i < k:
                mat[i][j], mat[k][j] = mat[k][j], mat[i][j]
                i += 1
                k -= 1

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count