Print numbers by spiral

Recently I came across simple yet interesting coding problem. So here is the deal. You are given positive integer N. Print first N ^ 2 positive integers in matrix form in a such a way that within matrix numbers form spiral starting from its center and goring clockwise. For example, for N = 5 matrix to be printed is:

21	22	23	24	25
20	7	8	9	10
19	6	1	2	11
18	5	4	3	12
17	16	15	14	13

Optimize it for speed and space.

One way you can approach it is to create N x N matrix and fill it with numbers that form spiral and then print whole matrix row by row. But this solution will be of N ^ 2 space complexity. Let’s try to reach O(1) space complexity.

The key observation here is how matrix changes when N changes by 1.

N = 1.

1

N = 2.

1	2
4	3

N = 3.

7	8	9
6	1	2
5	4	3

N = 4.

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

Can you see the pattern here? At every step we extend previous matrix (P) with additional column and row (C). If N is even we extend previous matrix of size N – 1 with right column and bottom row

P	C
C	C

and with left column and top row if it is odd

C	C
C	P

This leads us to naturally recursive algorithm. We have three cases:

1. Print whole row of the current matrix (top when N is odd or bottom when N is even).
2. Print row from previous matrix of size N - 1 first and then print value that belongs to current matrix (when N is even).
3. Print value that belongs to current matrix and then print row from previous matrix of size N - 1 (when N is odd).
4. Print matrix line by line.

So basically to print a row we need to know matrix size N and row index. Here goes the solution.

 static void Print(int n)
{
   for(int i = 0; i < n; i++)
   {
       PrintLine(n, i);
        Console.WriteLine();
    }
}

static void PrintLine(int n, int i)
{
  // Number of integers in current matrix
 var n2 = n*n;
   // Number of itegers in previous matrix of size n - 1
   var m2 = (n - 1)*(n - 1);

   if (n % 2 == 0)
 {
       if (i == n - 1)
     {
           // n is even and we are at the last row so just 
            // print it
         for(int k = n2; k > n2 - n; k--)
         {
               PrintNum(k);
            }
       }
       else
        {
           // Print row from previous matrix of size n - 1 
            // first and then print value that belongs to current 
          // matrix. Previous matrix is at the top left corner 
           // so no need to adjust row index
           PrintLine(n - 1, i);
            // Skip all integers from previous matrix and upper 
            // ones in this columnas integers must form clockwise 
          // spiral
           PrintNum(m2 + 1 + i);
       }
   }
   else
    {
       if (i == 0)
     {
           // n is odd and we are at the first row so just 
            // print it
         for(int k = m2 + n; k <= n2; k++)
            {
               PrintNum(k);
            }
       }
       else
        {
           // Print value that belongs to current matrix and
           // then print row from previous matrix of size n - 1
            // Skip all integers from previous matric and bottom
            // ones in this column as integers must form clockwise
          // spiral
           PrintNum(m2 + n - i);
           // Previous matrix is at the bottom right corner so
         // row index must be reduced by 1
           PrintLine(n - 1, i - 1);
        }
   }
}

static void PrintNum(int n)
{
  Console.Write("{0, -4}  ", n);
}

If stack is not considered then this solution has O(1) space complexity otherwise O(N).