/ Data Structure and Algorithms  

Leetcode 48. Rotate Image

Question



Rotate a 2D matrix by 90 degrees (clockwise). The rotation should be in-place (no extra space allocated).

Solution

To rotate 90 degrees clockwise, all we have to do is:

  1. Exchange by diagonal
  2. Exchange by center axis

See the graph for an illustration (image reference: https://zhuanlan.zhihu.com/p/58965148)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void rotate(int[][] matrix) {
    int size = matrix.length;

    // first rotate by diagonal
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            exchange(matrix, i, j);
        }
    }

    // then exchange by mid
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size / 2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][size - j - 1];
            matrix[i][size - j - 1] = temp;
        }
    }
}

// exchange matrix[i][j] and matrix[j][i] in the matrix
private void exchange(int[][] matrix, int i, int j) {
    int temp = matrix[i][j];
    matrix[i][j] = matrix[j][i];
    matrix[j][i] = temp;
}