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

## 2 comments:

sir. Would u be a bit more clear.... !!!!...... A detail algorithm is required........... Please help...

Post a Comment