# 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:

- Print whole row of the current matrix (top when N is odd or bottom when N is even).
- Print row from previous matrix of size N - 1 first and then print value that belongs to current matrix (when N is even).
- Print value that belongs to current matrix and then print row from previous matrix of size N - 1 (when N is odd).
- 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).