_48.java

package com.fishercoder.solutions;

/**
 * 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?
 */
public class _48 {

    //credit: https://discuss.leetcode.com/topic/9744/ac-java-in-place-solution-with-explanation-easy-to-understand
    public void rotate_O1(int[][] matrix) {
        /**First swap the elements on the diagonal, then reverse each row:
         * 1, 2, 3                    1, 4, 7                      7, 4, 1
         * 4, 5, 6         becomes    2, 5, 8           becomes    8, 5, 2
         * 7, 8, 9                    3, 6, 9                      9, 6, 3
         This could be done in O(1) space!
         **/
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = i; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }

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

    //credit: https://discuss.leetcode.com/topic/6796/a-common-method-to-rotate-the-image
    /**First swap the rows bottom up, then swap the element on the diagonal:
     * 1, 2, 3                         7, 8, 9                           7, 4, 1
     * 4, 5, 6           becomes       4, 5, 6           becomes         8, 5, 2
     * 7, 8, 9                         1, 2, 3                           9, 6, 3
     * */
    //however, this is using O(n) of extra space
    public void rotate_On(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int top = 0;
        int bottom = n-1;
        while (top < bottom){
            int[] tmp = matrix[top];
            matrix[top] = matrix[bottom];
            matrix[bottom] = tmp;
            top++;
            bottom--;
        }

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

}