Rotate Image

Problem Description

If you are given an n x n 2D matrix representing an image, rotate it by 90 degrees (clockwise). You have to rotate the image in place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

The rotation must be done in place, meaning you have to modify the given matrix directly without allocating extra space for another matrix.

Examples

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Explanation: Performing rotation in the given matrix

1 2 3                7 4 1
4 5 6     —>     8 5 2
7 8 9                9 6 3

Input: [[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]]
Explanation: Performing rotation in the given matrix

5   1   9   11              15  13  2   5
2   4   8   10     —>  14  3   4   1
13  3   6   7              12  6   8   9
15  14  12  16          16  7   10  11

Constraints

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

Intuition

Imagine you have a square grid, like a tic-tac-toe board, but larger. Each cell in this grid contains a number, and our goal is to rotate this grid by 90 degrees clockwise, like turning a picture frame. We want to achieve this without creating a new grid, meaning we need to rotate it in place—just by manipulating the original matrix.

The key idea is to understand how the elements in the matrix change their positions during a 90-degree rotation. Take a 3x3 matrix for example:

Before Rotation:          After Rotation:

1 2 3               7 4 1
4 5 6     —>   8 5 2
7 8 9              9 6 3

Notice how:

The element at the top-left corner (1) ends up in the top-right corner. The element in the top-right (3) moves to the bottom-right. The element in the bottom-right (9) moves to the bottom-left.

Looking at the entire grid, we see a pattern: each element’s row and column positions are rearranged to achieve the rotation.

• The first column of the original matrix, [1,4,7], has become the first row of the rotated matrix but in a reversed order: [7,4,1].
• The second row, [2,5,8], has become the middle row but in a reverse order: [8,5,2].
• Similarly, the third column, [9,6,3], has become the third column but in reverse order: [9,6,3].

In essence, rows turn into columns, and the order of elements within those rows is flipped.

This gives us a hint: rotating the matrix involves two key transformations. First, convert every column into a row. Then, reverse the order of elements in each row. These steps together produce the desired rotation.

Transpose of the matrix: Transposing a matrix means converting its rows into columns. This way, the diagonal remains the same, but all other elements are swapped.

For example, after transposing the 3x3 matrix, it looks like this:

Each element [i][j] gets swapped with [j][i], which moves it to the correct row for rotation.

Reverse each row: Once transposed, reversing each row gives us the final 90-degree clockwise rotation.

Reversing the rows results in:

So, the overall approach would be, to transpose the matrix to shift elements from rows to columns and Reverse each row to achieve the rotation effect.

Let's visualize it for a better understanding

class Solution {
public:
    // Function to rotate the matrix by 90 degrees clockwise
    void rotate(vector<vector<int>>& matrix) {

        // First step: Transpose the matrix
        for (int i = 0; i < matrix.size(); i++) {

            for (int j = i + 1; j < matrix[0].size(); j++) {

                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // Second step: Reverse each row
        for (int i = 0; i < matrix.size(); i++) {

            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

class Solution {

    // Function to rotate the matrix by 90 degrees clockwise
    public void rotate(int[][] matrix) {

        // First step: Transpose the matrix
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i + 1; j < matrix[0].length; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Second step: Reverse each row
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            for (int j = 0; j < row.length / 2; j++) {
                int temp = row[j];
                row[j] = row[row.length - j - 1];
                row[row.length - j - 1] = temp;
            }
        }
    }
}

class Solution:

    # Function to rotate the matrix by 90 degrees clockwise
    def rotate(self, matrix):
        # First step: Transpose the matrix
        for i in range(len(matrix)):
            for j in range(i + 1, len(matrix[0])):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # Second step: Reverse each row
        for i in range(len(matrix)):
            matrix[i].reverse()

class Solution {
    // Function to rotate the matrix by 90 degrees clockwise
    rotate(matrix) {
        // First step: Transpose the matrix
        for (let i = 0; i < matrix.length; i++) {
            for (let j = i + 1; j < matrix[0].length; j++) {
                [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
            }
        }

        // Second step: Reverse each row
        for (let i = 0; i < matrix.length; i++) {
            matrix[i].reverse();
        }
    }
}

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.