Rotate Image

Updated on 01 July, 2025
Rotate Image header image

Problem Statement

In this task, you are provided with an n x n 2D matrix that represents an image. Your objective is to rotate this matrix by 90 degrees in a clockwise direction. Importantly, the rotation must be performed in-place, meaning the original matrix should be directly modified without using an additional matrix for the operation.

Examples

Example 1

Input:

matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output:

[[7,4,1],[8,5,2],[9,6,3]]

Example 2

Input:

matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

Output:

[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints

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

Approach and Intuition

Rotating a matrix by 90 degrees clockwise involves repositioning the elements such that the rows become columns in a reversed manner. Here’s a step-by-step breakdown of the rotation process:

  1. Transpose the Matrix: First, swap the rows and columns of the matrix — this is called transposing. For any element located at position (i, j), after transposition, it will move to position (j, i).

  2. Reverse Each Row: After transposing, each row of the matrix should be reversed (i.e., the first element becomes the last, and so on). This reversal aligns the elements in the appropriate order to reflect a 90-degree clockwise rotation.

For instance, considering the matrix:

1 2 3
4 5 6
7 8 9
  • After transposing, it becomes:
1 4 7
2 5 8
3 6 9
  • Reversing each row results in:
7 4 1
8 5 2
9 6 3

The above actions achieve the desired transformation. This approach satisfies the in-place requirement as it modifies the matrix without utilizing extra space proportional to the matrix size. The constraints specified (with matrix sizes between 1x1 and 20x20 and element values ranging from -1000 to 1000) ensure that these operations are computationally feasible within the provided limits.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    void rotate90(vector<vector<int>>& matrix) {
        matrixTranspose(matrix);
        matrixReflect(matrix);
    }
    
private:
    void matrixTranspose(vector<vector<int>>& matrix) {
        int size = matrix.size();
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
    void matrixReflect(vector<vector<int>>& matrix) {
        int size = matrix.size();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size / 2; j++) {
                swap(matrix[i][j], matrix[i][size - j - 1]);
            }
        }
    }
};

The problem expects a square matrix to be rotated by 90 degrees to the right. This C++ implementation achieves that rotation using two primary operations:

  1. Transpose the Matrix: This changes rows into columns (and vice versa). Initiate a nested loop where i and j iterate through the indices. Only modify the upper triangle of the matrix to avoid re-transposing elements.

  2. Reflect the Matrix Horizontally: Flip the matrix horizontally using a vertical line through its center. Iterate through the outer loop by row and through the inner loop by the half of the matrix's columns to swap elements symmetrically from left to right.

These two transformations combined result in a 90-degree clockwise rotation of the original matrix:

  • First, transpose the matrix to reposition the elements.
  • Second, reflect the matrix to reorder the transposed elements into their correct rotated positions.

The overall time and space complexity for this operation is O(n^2), where n is the number of rows (or columns) in the matrix, as each element is considered exactly once or twice. This approach is effective for in-place matrix rotation without using additional memory for another matrix construct.

java
class Solution {
    public void rotateMatrix(int[][] grid) {
        swapDiagonal(grid);
        swapHorizontal(grid);
    }
    
    public void swapDiagonal(int[][] grid) {
        int len = grid.length;
        for (int row = 0; row < len; row++) {
            for (int col = row + 1; col < len; col++) {
                int temp = grid[col][row];
                grid[col][row] = grid[row][col];
                grid[row][col] = temp;
            }
        }
    }
    
    public void swapHorizontal(int[][] grid) {
        int len = grid.length;
        for (int row = 0; row < len; row++) {
            for (int col = 0; col < len / 2; col++) {
                int temp = grid[row][col];
                grid[row][col] = grid[row][len - col - 1];
                grid[row][len - col - 1] = temp;
            }
        }
    }
}

The Rotate Image problem requires modifying a matrix in-place to achieve a 90-degree rotation clockwise. The given solution in Java effectively addresses this by employing a two-step transformation process on the input grid:

  • Transpose the Matrix

    • Convert rows into columns, making the matrix symmetric along its diagonal. This transformation aligns elements into the position they should be based on their rows in the final rotated form.
  • Swap Columns Horizontally

    • Swap elements horizontally across the center, moving the first column to the last, and so on. This step completes the rotation by placing elements in their correct column positions post-rotation.

Perform the following steps in the code:

  1. Implement the swapDiagonal method:

    • Iterate over the matrix using nested loops, exchanging elements symmetrically across the diagonal without affecting elements on the diagonal itself.
  2. Execute the swapHorizontal method:

    • For each row, swap elements from the start with the corresponding elements from the end, effectively reversing the row elements up to the mid-column.

By calling these methods sequentially in rotateMatrix, the matrix rotates 90 degrees to the right in-place, ensuring the original matrix is transformed into its required final state without additional memory usage beyond constant variables. Ensure this transformation technique is used whenever an in-place matrix rotation is needed, especially when optimizing for space.

c
void transpose_and_flip(int** grid, int gridSize, int* gridColSize) {
    int swap_temp, size = gridSize;
    for (int row = 0; row < size; ++row) {
        for (int col = row + 1; col < size; ++col) {
            swap_temp = grid[row][col];
            grid[row][col] = grid[col][row];
            grid[col][row] = swap_temp;
        }
    }
    for (int row = 0; row < size; ++row) {
        for (int col = 0; col < size / 2; ++col) {
            swap_temp = grid[row][col];
            grid[row][col] = grid[row][size - col - 1];
            grid[row][size - col - 1] = swap_temp;
        }
    }
}

This solution involves rotating a square matrix clockwise by 90 degrees in C. The approach employs a two-step process on the given grid which represents the matrix:

  1. Transpose the Matrix: Swap the matrix elements along the diagonal. This step changes the rows into columns, effectively transposing the matrix. This is accomplished by iterating through the matrix and swapping the element at position (row, col) with the element at (col, row) for each pair of elements above the main diagonal.

  2. Reverse Each Row: After transposing, reverse the elements of each row to achieve the required rotation. This is handled by swapping the element at the start of the row with the corresponding element from the end of the row and moving inward until the center of the row is reached.

The above steps are performed in-place, meaning no additional matrices are required, using only a temporary variable to handle the swaps. This method ensures an efficient transformation with a time complexity of (O(n^2)), where n is the number of rows or columns of the square matrix.

Implement this solution to rotate a matrix efficiently while retaining a clean and manageable codebase.

js
var rotateMatrix = function (mat) {
    const size = mat.length;
    // Swap to transpose
    for (let i = 0; i < size; i++) {
        for (let j = i + 1; j < size; j++) {
            [mat[i][j], mat[j][i]] = [mat[j][i], mat[i][j]];
        }
    }
    // Swap to mirror horizontally
    for (let i = 0; i < size; i++) {
        for (let j = 0; j < size / 2; j++) {
            [mat[i][j], mat[i][size - 1 - j]] = [
                mat[i][size - 1 - j],
                mat[i][j],
            ];
        }
    }
};

This JavaScript function rotates an N x N matrix by 90 degrees clockwise. The function modifies the matrix in place, using only constant extra space for the element swaps. The function rotateMatrix follows these steps:

  1. Transpose the matrix:

    • Iterate through rows with variable i.
    • For each row, iterate through columns starting from i + 1 with variable j.
    • Swap elements at positions (i, j) and (j, i) in the matrix.
  2. Reverse each row:

    • Iterate through each row using variable i.
    • For each row, iterate through the first half of the columns with variable j.
    • Swap elements at positions (i, j) and (i, size - 1 - j).

This method relies on two main operations. The first is the transpose, where the matrix is converted such that rows become columns. The second operation mirrors each row horizontally to achieve the desired 90-degree rotation.

python
class Solution:
    def rotateMatrix(self, mat: List[List[int]]) -> None:
        self.matrixTranspose(mat)
        self.matrixReflect(mat)
    
    def matrixTranspose(self, mat):
        dimension = len(mat)
        for row in range(dimension):
            for col in range(row + 1, dimension):
                mat[col][row], mat[row][col] = mat[row][col], mat[col][row]
    
    def matrixReflect(self, mat):
        dimension = len(mat)
        for row in range(dimension):
            for col in range(dimension // 2):
                mat[row][col], mat[row][-col - 1] = mat[row][-col - 1], mat[row][col]

The Python function rotateMatrix, within the Solution class, is designed to rotate a given square matrix (n x n) by 90 degrees in a clockwise direction in-place. Here's an outline of how the function works:

  • rotateMatrix method: Calls two internal methods, matrixTranspose and matrixReflect sequentially. These transformations achieve the rotation effect without using additional storage for the matrix.

  • matrixTranspose method:

    1. Transposes the input matrix; converts rows into columns and vice-versa.
    2. Iterates over each element above the main diagonal and swaps it with its transposed counterpart, i.e., element (i, j) swaps with element (j, i).
  • matrixReflect method:

    1. Reflects the matrix about its vertical central axis.
    2. Iterates over each row and swaps elements symmetrically from the endpoints towards the center, i.e., the first element with the last, the second with the second last, and so on until the middle of the row is reached.

This approach ensures the matrix is rotated with minimal additional memory, leveraging symmetry and matrix properties effectively.

Comments

No comments yet.