Leetcode Study Day 17

2023-10-10

Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image 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.

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]]

Solution

Rotating a 2D matrix (or image) by 90 degrees in-place can be broken down into two steps:

Transpose the Matrix: This means converting all the rows of the matrix into columns.
1
2
3
a b

c d
becomes
1
2
3
a c

b d
Reverse the Columns: After transposition, the columns are reversed (or you can think of it as reversing each row).

Taking the transposed matrix from the example above:
1
2
3
a c

b d
becomes
1
2
3
c a

d b
which is the original matrix rotated 90 degrees clockwise.

Here’s a step-by-step breakdown:

Transpose the Matrix:
- Loop through the matrix.
- For each element at position ((i, j)), swap it with the element at position ((j, i)). Note: We only need to swap the elements once, so ensure that we are not swapping them back in a later iteration.

int length = matrix.size();
int start = 0;
for (int i = 0; i < length; i++){
    for (int j = start; j < length; j++){
        int cache = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = cache;
    }
    start ++;
}

Reverse the Columns:
- Loop through the matrix.
- For each row, reverse the elements in the row. This can be achieved by swapping the first element with the last, the second with the second last, and so on.

for (int i = 0; i < length  ; i ++){
    for (int j = 0; j < length/2; j++){
        int cache = matrix[i][length-1-j];
        matrix[i][length-1-j] = matrix[i][j];
        matrix[i][j] = cache;
    }
}

Full code

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int length = matrix.size();
        int start = 0;
        for (int i = 0; i < length; i++){
            for (int j = start; j < length; j++){
                int cache = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = cache;
            }
            start ++;
        }
        for (int i = 0; i < length  ; i ++){
            for (int j = 0; j < length/2; j++){
                int cache = matrix[i][length-1-j];
                matrix[i][length-1-j] = matrix[i][j];
                matrix[i][j] = cache;
            }
        }

    }
};