Rotating a Square Matrix Clockwise by 90 Degrees

Rotating a Square Matrix Clockwise by 90 Degrees

Rotating a square n×n matrix of integers clockwise by 90 degrees is a common programming challenge. This transformation must be performed in-place, meaning the rotation should not involve allocating a new 2D matrix.

Pair with given sum - Two Sum

Problem Statement

You are given an n×n matrix, represented as a list of lists. The task is to rotate this matrix 90 degrees clockwise, modifying the input matrix directly.

For instance:

Explanation:
Explanation:
The range [0, 3] contains the numbers {0, 1, 2, 3}. The number 0 is missing from the array nums.

Constraints 

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

There are mainly three approach to solve this problem – 

  1. Brute Force 
  2. Rotate By Four Cells
  3. Reverse And Transpose

1. Brute Force

  • Time complexity: 
  • Space complexity
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        rotated = [[0] * n for _ in range(n)]
        
        for i in range(n):
            for j in range(n):
                rotated[j][n - 1 - i] = matrix[i][j]
        
        for i in range(n):
            for j in range(n):
                matrix[i][j] = rotated[i][j]

2. Rotate By Four Cells 

Time & Space Complexity
    • Time complexity: O(n^2)
    • Space complexity: O(1)

Code

class Solution {
public:
    void rotate(vector>& matrix) {
        int l = 0;
        int r = matrix.size() - 1;
        
        while ( l < r ) {
            for(int i = 0; i < r - l; i++) {
                int top = l;
                int bottom = r;

                //save the topleft
                int topLeft = matrix[top][l + i];

                //move bottom left into top left
                matrix[top][l + i] = matrix[bottom - i][l];

                // move bottom right into bottom left
                matrix[bottom - i][l] = matrix[bottom][r - i];

                // move top right into bottom right
                matrix[bottom][r - i] = matrix[top + i][r];

                // move top left into top right
                matrix[top + i][r] = topLeft;
                
            }
            r--;
            l++;
        }
    }
};

3. Reverse And Transpose

  • Time complexity: O(n^2)
  • Space complexity: O(1)

Code

class Solution {
public:
    void rotate(vector>& matrix) {
        // Reverse the matrix vertically
        reverse(matrix.begin(), matrix.end());

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

More Articles