# 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).

Tags