Rotation of Matrix

Problem Statement

Rotate a matrix so that each loops do a rotation by 1.

If the input is :

1    2    3    4    
5    6    7    8
9    10   11   12
13   14   15   16

The output should be :

1    2    3    4    
5    6    7    8
9    10   11   12
13   14   15   16

Solution

Matrix in c# can be stored in multi-dimensional array or a jagged array. We are considering the solution using multi-dimensional array.The optimal solution would be to rotate each loop just once. So if the array size in MxN then the number of element in outer loop would be : M + M + N + N – 4. We reduced 4 because the corner got included twice.

To get the element in inner loop, the same formula can be used but now with reduction in size of M and N by 2. So the count would be (M-2) + (M-2) + (N-2) + (N-2) -4. We reduced two since the inner loop would have 1 less element on both end of the array.

As you can see from the diagram, we need to loop 4 times in this case. The number of element in each loop can be derived by adding rows and column and removing duplicate. The other thing to notice is that the number of loop will be the MIN(M,N)/2 + 1. This is pretty obvious because the number loop will be the half of the shortest side.

Below is the C# code. The code accept any array and rotates it. The display function has some formatting display logic which can be ignored:

 using System;

namespace LGO
{
    class Program
    {
        static void Main(string[] args)
        {
            int [,] matrix = new int[,] {   {01,02,03,04,05,06,07},
                                            {26,30,31,32,33,34,35},
                                            {25,47,50,51,52,53,36},
                                            {24,46,59,60,61,54,37},
                                            {23,45,58,57,56,55,38},
                                            {22,44,43,42,41,40,39},
                                            {21,20,19,18,17,16,15}
                                            };

            display(matrix);
            rotate(matrix);
            display(matrix);

        }

        public static void rotate(int[,] matrix)
        {
            int numberofLoops = matrix.GetLength(0) > matrix.GetLength(1) ? (matrix.GetLength(1)+1)/2 : (matrix.GetLength(0)+1)/2;
            int row=0, col=0, toVal=0, fromVal = 0 , maxInLoop, maxCol , maxRow , nextCol = 0, nextRow = 0;
            for(int i = 0; i<numberofLoops; i++)
            {
                maxCol = matrix.GetLength(1)-1-i;
                maxRow = matrix.GetLength(0)-1-i;
                row = col = i;
                toVal = matrix[row, col];
                maxInLoop = 2*(matrix.GetLength(0)-2*i) + 2*(matrix.GetLength(1)-2*i) - 4;
                for(int j=0; j< maxInLoop; j++)
                {
                    fromVal = toVal;
                    if(row == i && col <  maxCol)
                    {    
                        nextCol = col + 1;
                        toVal = matrix[row, nextCol];
                        matrix[row, nextCol] = fromVal;
                        col++; 
                    }
                    
                    else if(row < maxRow && col ==  maxCol)
                    {   
                        nextRow = row + 1; 
                        toVal = matrix[nextRow, col];
                        matrix[nextRow, col] = fromVal; 
                        row++;    
                    }
                    else if(row == maxRow && col >  i)
                    {
                        nextCol = col - 1;
                        toVal = matrix[row, nextCol];
                        matrix[row, nextCol] = fromVal;   
                        col--;
                    }    
                    else if(row > 0 && col ==  i)
                    {
                        nextRow = row - 1;
                        toVal = matrix[nextRow, col];
                        matrix[nextRow, col] = fromVal;  
                        row--; 
                    }
                }
            }
        }
        public static void display(int[,] matrix)
        {
            for(int i = 0; i< matrix.GetLength(0); i++)
            {    for(int j=0; j< matrix.GetLength(1);j++)
                {
                    Console.Write(matrix[i,j]);
                    int length = matrix[i,j]/10 < 1 ? 3 : (matrix[i,j]/10 < 10 ? 2 : 1);
                    for(int k=0;k<length;k++)
                        Console.Write(" ");
                }
                Console.WriteLine();
            }    
        }
    }
}