Rotate Matrix - C++ Solution

1. Introduction

The "Rotate Matrix" problem is a common algorithmic challenge that deals with the manipulation of 2D arrays or matrices. It requires rotating an N × N matrix by 90 degrees in a clockwise direction, and the rotation must be performed in-place to maintain space efficiency.

Problem

Given an N × N integer matrix, the task is to rotate the matrix by 90 degrees in a clockwise direction. The rotation should be done in-place, meaning without using any additional space, and in quadratic time complexity.

2. Solution Steps

1. Transpose the matrix: Swap matrix[i][j] with matrix[j][i].

2. Reverse each row of the transposed matrix.

3. The combination of these two steps results in a 90-degree clockwise rotation.

3. Code Program

#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; 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());
    }
}

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

    rotateMatrix(matrix);

    // Print the rotated matrix
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

13 9 5 1

Explanation:

The program first transposes the matrix by swapping the elements at matrix[i][j] with matrix[j][i]. This step aligns rows into columns. 

Then, each row of the transposed matrix is reversed, effectively rotating the matrix by 90 degrees clockwise. 

This in-place transformation ensures that no additional space is used, and the operation's quadratic time complexity is suitable for N × N matrices.