[LeetCode] 48. Rotate Image

Posted on | In

Problem

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Explanation

  1. From the example 2’s input array, we can think of four groups and from outside to inside. For example, outside, [5, 1, 9], [11, 10, 7], [16, 12, 14], and [15, 13, 2].

  2. We need four variables top, left, bottom, right to indicate the position of four group’s first number.

  3. Before we start, use the variable n to indicate the length of the square we are moving is greater than 1 because we cannot rotate the 1x1 square. We move group1 to group2, group2 to group3, group3 to group4, group4 to group1. We want to loop each group’s number, so inside a loop, we first put group1’s number to a temp variable, then we move group4’s first number to group1’s first number, then move group 3’s first number to group4’s first number, then move group2’s first number to group1’s first number, then move the temp to group2’s corresponding number. After finish the first number, we iterate the next number and move the second number in the group, etc. For example group4 to group1, we move 15 to 5, 13 to 1, 2 to 9, etc.

  4. After we finish the outside one, we try the inside and we need to update the length and top, left, bottom, right. From the example2, we update from 4x4 to 2x2, and the four groups are: [4], [8], [6], [3]. Then we follow the above step and move each group’s number until then length become 1x1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        
        int top = 0, left = 0, bottom = matrix.length-1, right = matrix[0].length-1;
        int n = matrix.length;
        
        while (n > 1) {
            for (int i = 0; i < n-1; i++) {
                int temp = matrix[top][left+i];
                matrix[top][left+i] = matrix[bottom-i][left];
                matrix[bottom-i][left] = matrix[bottom][right-i];
                matrix[bottom][right-i] = matrix[top+i][right];
                matrix[top+i][right] = temp;
            }
            top++;
            left++;
            bottom--;
            right--;
            n -= 2;
        }
    }
}