48. Rotate Image

LeetCode

Math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void rotate(int[][] matrix) {
        int tmp = 0;
        int n = matrix.length;

        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) { 
                // swap the four blocks sequently
                tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
}

Remarks:

  1. Be carefull of the index: we start from nums[0][0] but not nums[1][1]!

    How blocks rotate: nums[i][j] -> nums[j][n - j - 1].

  2. TC: $O(n^2)$, SC: $O(1)$

  3. No need to process the center point (when n is odd).