Algorithm, Rotate matrix nxm clockwise 90 degree

April 5, 2016

  Write an algorithm to rotate matrix nxm clockwise 90 degree.

  Use no compiler, no Ctrl+C, and then, time complexity analysis:

Here is the code Julia wrote, she thought about the swapping strategies:
1. swap multiple times
2. leave four corners as is, swap four corners seperately.

https://gist.github.com/jianminchen/e489cf7a490ac426eb50b4300890387d

/*
April 5, 2016

NO ctrl+C copy

matrix nxm rotate clockwise 90 degree

do it in place
*/

 public static bool rotateInplace90ClockWise(int[][] arr)
        {
            if (arr == null || arr.Length == 0 || arr[0].Length == 0) return false;
            int n = arr.Length;      // row
            int m = arr[0].Length;   // column

            if (n != m) return false;

            // we need to start loops

            int start = 0;
            int end = n - 1;

            while (start < end && start < n / 2 && end < n / 2)
            {

                // top with right swap - left the terminal point untouched
                // left to right <- row
                // top to down   <- column
                for (int i = start + 1; i < end - 1; i++)
                {
                    int currx = start;
                    int curry = i;

                    int currx_col = i;
                    int curry_col = end;

                    swap(arr, currx, curry, currx_col, curry_col);
                }

                // now, top down, we need to cross swap

                for (int i = start + 1; i < end - 1; i++)
                {
                    int currx = start;
                    int curry = i;

                    int currx_down = end;
                    int curry_down = end - i;

                    swap(arr, currx, curry, currx_down, curry_down);
                }

                // left and top swap
                for (int i = start + 1; i < end - 1; i++)
                {
                    // left part
                    int currx = end - 1 - i;
                    int curry = start;

                    int currx_top = start;
                    int curry_top = i;

                    swap(arr, currx, curry, currx_top, curry_top);
                }

                // and then, rotate four corners
                // 1, 2
                // 4  3
                swap(arr, start, start, start, end);
                swap(arr, end, end, start, start);
                swap(arr, start, start, end, start);

                start++;
                end--;
            }
            return true;
        }
 
       private static void swap(int[][] arr, int x, int y, int x2, int y2)
       {
           int tmp     = arr[x][y];
           arr[x][y]   = arr[x2][y2];
           arr[x2][y2] = tmp;
       }

https://gist.github.com/jianminchen/e489cf7a490ac426eb50b4300890387d

time complexity: since every node in the matrix at most swaps twice, so the count of swap is O(n^2)