Rotate a Matrix by 90 degrees

Given an N x N matrix, rotate the matrix by 90 degrees in a clockwise direction. The rotation should be done in-place, meaning no additional matrix should be used.

Input/Output Examples

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

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

Explanation: The matrix is rotated 90 degrees clockwise.

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]]
Explanation: The matrix is rotated 90 degrees clockwise.

Approach to Rotate a Matrix

  1. Transpose the Matrix:
    • Swap elements across the diagonal (i.e., swap matrix[i][j] with matrix[j][i] for i < j). This step turns rows into columns.
  2. Reverse Each Row:
    • Reverse the elements of each row. This step completes the 90-degree clockwise rotation of the matrix.
  3. In-place Rotation:
    • Perform the rotation directly on the matrix without using additional storage.

C++ Program to Rotate a Matrix

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

// Function to rotate the matrix by 90 degrees clockwise
void rotateMatrix(vector<vector<int>>& matrix) {
    int n = matrix.size();

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

    // Reverse each row
    for (int i = 0; i < n; i++) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
}

// Function to print the matrix
void printMatrix(const vector<vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    rotateMatrix(matrix);

    cout << "Rotated Matrix:" << endl;
    printMatrix(matrix);

    return 0;
}

Java Program to Rotate a Matrix

java
public class RotateMatrix {

    // Function to rotate the matrix by 90 degrees clockwise
    public static void rotateMatrix(int[][] matrix) {
        int n = matrix.length;

        // Transpose the matrix
        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 each row
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }

    // Function to print the matrix
    public static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            for (int val : row) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }

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

        rotateMatrix(matrix);

        System.out.println("Rotated Matrix:");
        printMatrix(matrix);
    }
}

Python Program to Rotate a Matrix

python
# Function to rotate the matrix by 90 degrees clockwise
def rotate_matrix(matrix):
    n = len(matrix)

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

    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

# Function to print the matrix
def print_matrix(matrix):
    for row in matrix:
        print(" ".join(map(str, row)))

# Example usage
if __name__ == "__main__":
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]

    rotate_matrix(matrix)

    print("Rotated Matrix:")
    print_matrix(matrix)
  • Time Complexity: O(N^2) where N is the size of the matrix, as we need to process each element twice (once for transposing and once for reversing).
  • Space Complexity: O(1) since the rotation is done in-place, using no additional space for another matrix.

DSA

5251

198

Related Articles