Problem Statement
Given a square integer matrix "matrix" of size n x n. The matrix represents values arranged in rows and columns, and the required rotation is 90 degrees clockwise. Rotate matrix in-place.
Return nothing after the rotation.
Example 1
Input: matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
Output: [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]]
Explanation: The first column becomes the first row after rotation, but its order is reversed. The same mapping is applied to every column.
Example 2
Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Explanation: Each value moves to its clockwise-rotated position around the center of the square matrix.
Brute Force Approach
Every value can be placed into a separate matrix at its final rotated position. For a value currently at row r and column c, the clockwise destination is row c and column n - 1 - r.
After all values are copied to their rotated positions, the temporary matrix is copied back into the original matrix. This is direct and easy to verify, but it does not satisfy the strict in-place space goal because it stores another n x n matrix.
Algorithm
Create a temporary square matrix with the same size as the input matrix.
For every cell in the original matrix, compute its clockwise destination using the row-column mapping.
Store the current value in the destination cell of the temporary matrix.
Copy every value from the temporary matrix back into the original matrix.
Dry Run
Rotate Matrix
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Rotates the square matrix by 90 degrees clockwise. void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); vector<vector<int>> rotated(n, vector<int>(n)); // Place each value at its clockwise-rotated destination. for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { rotated[col][n - 1 - row] = matrix[row][col]; } } // Copy the rotated arrangement back into the original matrix. for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { matrix[row][col] = rotated[row][col]; } } }};// Prints the matrix row by row.void printMatrix(vector<vector<int>>& matrix) { cout << '['; // Print commas only between neighboring rows. for (int row = 0; row < matrix.size(); row++) { // A comma is needed before every row except the first one. if (row > 0) { cout << ", "; } cout << '['; // Print commas only between neighboring values. for (int col = 0; col < matrix[row].size(); col++) { // A comma is needed before every value except the first one. if (col > 0) { cout << ", "; } cout << matrix[row][col]; } cout << ']'; } cout << "]\n";}// Driver codeint main() { vector<vector<int>> matrix = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; // instance for class Solution Solution sol; sol.rotate(matrix); printMatrix(matrix); return 0;}Complexity Analysis
Time Complexity: O(n²), because all n² cells are read once and copied back once.
Space Complexity: O(n²), because a separate n x n matrix is used.
Optimal Approach
In the rotated matrix, the first column of the original matrix becomes the first row of the output matrix in reverse order. For the sample matrix, [1, 5, 9, 13] becomes [13, 9, 5, 1]. The same pattern holds for every column: each original column becomes one row after rotation, read from bottom to top.
This observation leads naturally to transposition. A transpose changes columns into rows by swapping values across the main diagonal. After transposition, every row contains the correct set of values for the rotated matrix, but the order inside each row still needs to be reversed.
So the rotation can be completed in two transformations: transpose the matrix, then reverse every row.
Algorithm
Swap values across the main diagonal to transpose the matrix in place.
During transposition, only swap cells above the diagonal with their matching cells below the diagonal.
After the transpose is complete, reverse each row of the matrix.
Keep every reversal in place so no additional matrix is created.
Stop after all rows have been reversed.
Dry Run
Rotate Matrix - Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Rotates the square matrix by 90 degrees clockwise. void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); // Transpose the matrix by swapping across the main diagonal. for (int row = 0; row < n; row++) { for (int col = row + 1; col < n; col++) { swap(matrix[row][col], matrix[col][row]); } } // Reverse every row to complete the clockwise rotation. for (int row = 0; row < n; row++) { reverse(matrix[row].begin(), matrix[row].end()); } }};// Prints the matrix row by row.void printMatrix(vector<vector<int>>& matrix) { cout << '['; // Print commas only between neighboring rows. for (int row = 0; row < matrix.size(); row++) { // A comma is needed before every row except the first one. if (row > 0) { cout << ", "; } cout << '['; // Print commas only between neighboring values. for (int col = 0; col < matrix[row].size(); col++) { // A comma is needed before every value except the first one. if (col > 0) { cout << ", "; } cout << matrix[row][col]; } cout << ']'; } cout << "]\n";}// Driver codeint main() { vector<vector<int>> matrix = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; // instance for class Solution Solution sol; sol.rotate(matrix); printMatrix(matrix); return 0;}Complexity Analysis
Time Complexity: O(n²), because transposition touches roughly half the matrix and row reversal touches all rows.
Space Complexity: O(1), because the matrix is modified in place with only temporary variables.
Interview follow-up Questions
Transposition moves the value at (r, c) to (c, r). Reversing that transposed row moves it from column r to column n - 1 - r, so the final position becomes (c, n - 1 - r), exactly the clockwise rotation mapping.
Be the first to add a comment.