Matrix Rotation Editorial

Practice Problem Link: Matrix Rotation | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a matrix, rotate the matrix 90 degrees clockwise.

Approach

This is a problem where the naive and optimal approaches will have the same complexity of space and time. The key thing in this problem is to observe what exactly is happening in a 90-degree rotation.

Observe that a 90-degree clockwise rotation can be broken up into 2 simpler operations, the superposition of which gives the required rotation.

The operations are “Transpose” (interchanging the rows and the columns), and “Row Reversal”.

By applying these 2 operations, one after another to the matrix, we can obtain the 90-degree rotated matrix.

Analysis

• Time Complexity: O(numRows * numCols)
• Space Complexity: O(numRows * numCols)

Implementation

C++

vector<vector<int> > rotateMatrix(vector<vector<int> > &matrix){
   int numRows = matrix.size();
   int numCols = matrix[0].size();
   vector<vector<int>> rotatedMatrix(numCols, vector<int> (numRows));
   for (int i = 0; i < numRows; i++) {
       for (int j = 0; j < numCols; j++) {
           rotatedMatrix[j][i] = matrix[i][j];
       }
   }
   for(auto &x: rotatedMatrix) {
       reverse(x.begin(), x.end());
   }
   return rotatedMatrix;
}

Java

class Solution {
   int[][] rotateMatrix(int[][] matrix){
       int numRows = matrix.length;
       int numCols = matrix[0].length;
       int rotatedMatrix[][] = new int[numCols][numRows];
       for (int i = 0; i < numRows; i++) {
           for (int j = 0; j < numCols; j++) {
               rotatedMatrix[j][i] = matrix[i][j];
           }
       }
       for(int i = 0; i < numCols; i++) {
           int start = 0, end = numRows - 1;
           while(start < end) {
               int temp = rotatedMatrix[i][start];
               rotatedMatrix[i][start] = rotatedMatrix[i][end];
               rotatedMatrix[i][end] = temp;
               start++;
               end--;
           }
       }
       return rotatedMatrix;
   }
}