rotate array

April 12, 2016

Rotate array one element to right or down, clockwise.

For example:
1 2 3
8 9 4
7 6 5

After rotation, the matrix is the following:
8 1 2
7 9 3
6 5 4

Practice: (Time spent: 1 hour)
https://gist.github.com/jianminchen/24d77970e9a58a7850f2add10dfe7c4f

Failed test case:
1 2
4 3

output should be:
4 1
3 2

but my result:
3 2
4 1

Bug fix: (Time spent: 20+ minutes)
https://gist.github.com/jianminchen/6eb6244fbb1912e3a06e672f604f87e0

        /*
         * Do it in place
         */
        public static bool rotateArray(int[][] arr, int k)
        {
            if (arr == null) return false;
            int n = arr.Length;  // row
            int m = arr[0].Length; // column

            if (n != m) return false;
            if (n != k) return false;

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

            while (start <= end && start < k / 2)
            {
                // for left column
                swap(arr, start, start, start, start + 1, k);
                for (int i = start + 1; i <= end; i++)
                {
                    swap(arr, i, start, i - 1, start, k);
                }

                // for down row - swap
                for (int i = start; i < end; i++)
                {
                    swap(arr, end, i, end, i + 1, k);
                }
                // for right column
               // for (int i = end; i > start; i--)  // bug 001  if there are only two rows, exception
                for (int i = end; i > start && (end-start) > 1; i--)  // bug001 fix - do not swap if there are two rows
                {
                    swap(arr, i, end, i - 1, end, k);
                }
                // for up row              
                for (int i = end; i > start + 2; i--)
                {
                    swap(arr, start, i, start, i - 1, k);
                }
                start++;
                end--;
            }
            return true;
        }

Action item:
Base case 1x1,  2x2, and then 3X3, you cannot skip 2x2. It doesn't t matter what test case is given. Think about basics.

Also, think about how many swaps are needed for
1 2
4 3
only 3 swaps:
First one,
1 and 2
1 2
second one:
2 and 4
2
4
third one:
2 and 3
2 3

<- and then, need to filter out last 2 swaps in the while loop.

Relax, take more practice:
Smart to use debugger:
https://www.quora.com/Does-using-debugger-help-a-lot-in-competitive-programming

https://www.quora.com/What-are-the-best-competitive-programming-debugging-tips

April 15, 2016
Better design is to save arr[0][0] value, and then shift array value to left on top row. Make corner case much easy to handle.
So, good ritual is to come out more than 1 idea, and then, compare which one is better. Ask why!

Swap value cannot beat the array shift, much simpler the later one.