Matrix Rotation

Question

Given a NxN matrix, where each element in the matrix is integer, write a method to rotate the matrix by 90 degrees.

Answer

We can separate the question to a set of small questions. The matrix could be considered as N/2 layers, which is a circle from innermost to outermost. So the key is swapping the element in each circle.

For example, we have a matrix:

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

At first time of computing, in layer one, it’s 1,2,3,4,5, 5,10,15,20,25, 25,24,23,22,21 and 21,16,11,6,1(It’s edges at the outermost). We start from the first element, so move 1 to 5, 5 to 25, 25 to 21 and 21 to 1. Yes it’s a cyclic swap, four times in all. Why four times? Because it’s a matrix and it has four corners. After this action:

21	2	3	4	1
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
25	22	23	24	5

Then we move 2 to 4, 4 to 19, 19 to 17 and 17 to 2.

…

After N - 1 times, the matrix is:

21	16	11	6	1
22	7	8	9	2
23	12	13	14	3
24	17	18	19	4
25	22	15	10	5

We can find out the outermost layer of the matrix has been completely rotated. Then we need to handle the second layer, which is(except 13, we needn’t take care about it as 13 at the centre point, so there is no third layer):

7	8	9
12	13	14
17	18	19

…

After process all the N/2 layers, the matrix will be completely rotate:

21	16	11	6	1
22	17	12	7	2
23	18	13	8	3
24	19	14	9	4
25	20	15	10	5

Whole java file

package example;

public class Matrix {

    /**
     * Rotate a matrix, space complexity is O(1), time complexity is O(2N)
     * @param matrix the matrix to be rotated
     */
    public static void rotate(int[][] matrix) {
        for (int i = 0; i < matrix.length / 2; i++) {
            int[] layer = matrix[i];
            for (int j = i; j < matrix[i].length - i - 1; j++) {
                exchange(matrix, layer[j], i, j, 0);
            }
        }
    }

    /**
     * Exchange the element in matrix
     * @param matrix
     * @param val The value want to replace to other element
     * @param layer The layer of the value
     * @param index The index of the value
     * @param times The times of the recursion function has been invoked. Because of it's a matrix, so after invoked for 3 times, it will return to the beginning position
     */
    private static void exchange(int[][] matrix, int val, int layer, int index, int times) {
        if (times > 4) {
            return;
        }
        int tmp = matrix[index][matrix[index].length - layer - 1];
        exchange(matrix, tmp, index, matrix[index].length - layer - 1, ++times);
        matrix[index][matrix[index].length - layer - 1] = val;
        Matrix.printMatrix(matrix);
    }

    public static void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + ",");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }

    public static void main(String[] args) {
        int[][] matrix = { {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} };

        Matrix.printMatrix(matrix);
        Matrix.rotate(matrix);
        Matrix.printMatrix(matrix);
    }

}