LeetCode 48 Rotate Image

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

Difficulty
Medium

Related Problems
[LeetCode 54] Spiral Matrix [LeetCode 59] Spiral Matrix II

Analysis

We need to have some basic knowledge of matrix and transpose matrix. In math, the transpose of a matrix A is another matrix AT created by reflecting A over its main diagonal (which runs from top-left to bottom-right).

e.g.

Idea 1 Transpose, than reverse each horizontal line

1    2        1  |  3        3    1
   \    --->     |     --->
3    4        2  |  4        4    2

Idea 2

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

We can take a matrix as composed of multiple rings. e.g.

the outer ring is 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 1 the inner ring is 6, 7, 11, 10。

rotate a matrix is equivalent of rotaing each ring, how do we rotate a ring?

Fot the outmost ring:

Before rotate:

1   2   3   4      |1         4 | |     2      |  |        3     |
5           8      |            | |           8|  |5             |
9           12     |            | |9           |  |            12|
13  14  15  16     |13        16| |         15 |  |    14        |

After rotate:

13  9   5   1
14          2
15          3
16  12  8   4

We divide the ring into 3 parts: {1, 4, 16, 13}, {2, 8, 15, 9}, {3, 12, 14, 5}

For each part, rotate by 90 degree means we put an item to its next item's positon.

For a n * n matrix, we can divide it into n/2 rings to make the rotation. e.g.

Given 4 4 matrix, we need to process 4/2 => 2 rings, the outer has width 4, the inner has width 2.
Given 3 3 matrix, we need to process 3/2 => 2 rings, the outer has width 3, the inner has only 1 element.
Given 2 * 2 matrix, we need to process 2/2 => 1 ring.

For a ring (rectangle) with width len, we can split it into len - 1 parts to make the rotation.

Idea 2 has a better performance then Idea 1 since Idea 1 take two times swapping operations.

Solutions

1. Cpp solution 6ms

class Solution {
public:
    void rotate(vector<vector<int>> &matrix) {
        int n = matrix.size();
        // tranpose
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
                swap(matrix[i][j] , matrix[j][i]);
        // reverse each line
        for(int i = 0; i < n; i++)
            for(int j = 0; j < (n>>1); j++)
                swap(matrix[i][j], matrix[i][n-j-1]);
    }
};

1. Cpp solution 3ms

class Solution {
public:
    void rotate(vector<vector<int>> &matrix) {
        int n = matrix.size();  // n is the dimension
        if(n == 0) return;

        // n/2 is the number of rings we need to process, len is the rectange length of the i-th ring.
        // from outer to inner rings, the len -= 2.

        for(int i = 0, len = n; i < n/2; i++, len -= 2){ 
            int m = len - 1; 
            for(int j = 0; j < m; j++){
                int tmp = matrix[i][i + j];
                matrix[i][i + j] = matrix[i + m - j][i];              // [0][0] = [2][0]
                matrix[i + m - j][i] = matrix[i + m][i + m - j];      // [2][0] = [2][2]
                matrix[i + m][i + m-  j] = matrix[i + j][i + m];      // [2][2] = [0][2]
                matrix[i + j][i + m] = tmp;                           // [2][2] = [0][0]
            }
        }
    }
};

e.g.

1 2 3       1   3         2
4 5 6   -->        and  4   6   and  5
7 8 9       7   9         8

Process demo

  i = 0, 1, 2, 3
len = 3, 1
  m = 2, 0
  j = 0, 1

1   3       [0][0] = [2][0]
            [2][0] = [2][2]
7   9       [2][2] = [0][2]
            [2][2] = [0][0]


  2         [0][1] = [1][0]
4   6       [1][0] = [2][1]
  8         [2][1] = [1][2]
            [1][2] = [0][1]

  5         won't go into loop as m == 0, j < m condition failed.

1. Go solution ```go func rotate(matrix [][]int) { n := len(matrix) for i := 0; i < n; i++ {

    for j := i + 1; j < n; j++ {
        // matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        swap(&matrix[i][j], &matrix[j][i])
    }
   

   } for i := 0; i < n; i++ {

    for j := 0; j < n/2; j++ {
        // matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
        swap(&matrix[i][j], &matrix[i][n-j-1])
    }
   

   } }

func swap(a, b int) { a, b = b, *a } ```

Reference