Wednesday, May 25, 2016

Print n x n spiral matrix using O(1) extra space - GeeksforGeeks

Print n x n spiral matrix using O(1) extra space - GeeksforGeeks
Given a number n, print a n x n spiral matrix (of numbers from 1 to n x n) in clockwise direction using O(1) space.

The solution becomes simple if extra space is allowed. We allocate memory for n x n matrix and for every element starting from n*n to 1, we start filling out matrix in spiral order. To maintain the spiral order four loops are used, each for top, right, bottom and left corner of the matrix.
`void` `printSpiral(``int` `n)`
`{`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``for` `(``int` `j = 0; j < n; j++)`
`        ``{`
`            ``// x stores the layer in which (i, j)th`
`            ``// element lies`
`            ``int` `x;`

`            ``// Finds minimum of four inputs`
`            ``x = min(min(i, j), min(n-1-i, n-1-j));`

`            ``// For upper right half`
`            ``if` `(i <= j)`
`                ``printf``(``"%2d "``, (n-2*x)*(n-2*x) - (i-x)`
`                       ``- (j-x));`

`            ``// for lower left half`
`            ``else`
`                ``printf``(``"%2d "``, (n-2*x-2)*(n-2*x-2) + (i-x)`
`                       ``+ (j-x));`
`        ``}`
`        ``printf``(``"\n"``);`
`    ``}`
`}`

For a given number n, print a n x n spiral matrix in counter clockwise direction using O(1) space.