48. Rotate Image


  • 0
    H

    0_1507608775104_Screen Shot 2017-10-10 at 12.11.43 AM.png
    0_1507608802119_Screen Shot 2017-10-10 at 12.12.04 AM.png

    Solution

    Algorithm

    We begin by understanding how to rotate a 2x2, 3x3, and 4x4 matrix to understand the algorithm.

    0_1507609432810_Screen Shot 2017-10-10 at 12.23.19 AM.png

    1. In order to rotate a 2x2 matrix,
      • The element at [0,0] is swapped with the element at [0,1], [1,1], and [1,0] in that order.
    2. In order to rotate a 3x3 matrix,
      • The element at [0,0] is swapped with the element at [0,2], [2,2], and [2,0] in that order.
      • The element at [0,1] is swapped with the element at [1,2], [2,1], and [1,0] in that order.
    3. In order to rotate a 4x4 matrix
      • The element at [0,0] is swapped with the element at [0,3], [3,3], and [3,0] in that order.
      • The element at [0,1] is swapped with the element at [1,3], [3,2], and [2,0] in that order.
      • The element at [0,2] is swapped with the element at [2,3], [3,1], and [1,0] in that order.
      • The last step involves rotating the inside 2x2 matrix the exact same way the 2x2 matrix is rotated above.
        • The element at [1,1] is swapped with the element at [1,2], [2,2], and [2,1] in that order.



    Java Solution

    class Solution {
        public void rotate(int[][] matrix) {
            int last = matrix.length - 1;
            int level = 0;
            int numOfLevels = matrix.length/2;
            
            while(level < numOfLevels){
                for(int i=level; i<last; i++){
                    swap(level, i, i, last, matrix);
                    swap(level, i, last, last - i + level, matrix);
                    swap(level, i, last - i + level, level, matrix);
                }
                level++;
                last--;
            }
        }
        void swap(int i1, int j1, int i2, int j2, int[][] arr){
            int t = arr[i1][j1];
            arr[i1][j1] = arr[i2][j2];
            arr[i2][j2] = t;
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.