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.
Comments
Post a Comment